Insert Interval: Finding Union

First Thoughts

일단 시작시간을 이용해서 들어갈 자리를 찾는다. 앞뒤의 시간 배열 사이에 들어가는지 확인하며 merge과정을 진행한다. 근데 생각보다 후자가 쉽지 않았다. merge해야되는 경우가 꽤 많았던 걸로 기억한다. 중간에 있는 것도 처리해주지만, 바로 이어지는 경우도 처리해줘야했다. merge를 할때마다 또 merge될 가능성이 있으므로 그것도 pointer를 다시 원상복귀 해야한다.

My Solution

 public int[][] insert(int[][] intervals, int[] newInterval) {
        if (intervals == null || intervals.length == 0 || intervals[0].length == 0) {
            int[][] ret = {newInterval};
            return ret;
        }
        ArrayList<int[]> list = new ArrayList<>(Arrays.asList(intervals));
        int position = 0;
        for (int i=0; i<intervals.length; i++) {
            if (intervals[i][0]>newInterval[0]) {
                list.add(i, newInterval);
                break;
            } 
        }
        mergeList(list);
        int[][] ret = new int[list.size()][];
        for (int i=0; i<list.size(); i++) ret[i] = list.get(i);
        return ret;
    }
    public void mergeList(ArrayList<int[]> list) {
        for (int i=0; i<list.size()-1; i++) {
            int[] first = list.get(i);
            int[] second = list.get(i+1);
            if (second[0]>=first[0] && second[0]<=first[1]) {
                int laterTime = second[1] > first[1] ? second[1] : first[1];
                int[] merged = {list.get(i)[0], laterTime};
                list.remove(i);
                list.remove(i);
                list.add(i, merged);
                i--;
            }
        }
    }

Simpler Solution

public int[][] insert(int[][] intervals, int[] newInterval) {
	ArrayList<int[]> list = new ArrayList<>();
    int[] time = newInterval;
    
    for (int i=0; i<intervals.length; i++) {
    	if (intervals[i][0] > time[1]) {
        	list.add(time);
            time = intervals[i];
        }
        else if (intervals[i][1] <= time[0]) {
        	time = new int[] {
            Math.min(intervals[i][0], time[0]),
            Math.max(intervals[i][1], time[1])};
        }
        else list.add(intervals[i]);
    }
    list.add(time);
    return list.toArray(new int[list.size()][2]);
}

Catch Point

1. 완전히 새로운 배열을 만들면 무엇을 먼저 배열에 추가할지 고를 수 있게된다. 이때 추가할 시간배열 (time)도 수정가능함으로 코드가 더 간결해질 수 있다 -> 따로 merge하는 helper method가 필요없어진다.

2. 새로운 시간배열을 만들때 두 시간배열의 최소 시작시간과 최대 끝나는 시간으로 맞춰준다.

3. 새로운 배열 (time)은 마지막에 또 더해준다..