56. Merge Intervals

Problem:

Given a collection of intervals, merge all overlapping intervals.

Example:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considerred overlapping.

Analysis:

Approach 1: Sort intervals

Sort interval by start, compare with adjacent intervals. If they over lap then update end. 

Interval 0 and interval 1 overlap, so we update the new interval's end to e2. When we reach interval 3, we know that we can add the prev interval to result list. There is a case when one interval wraps another one. So we can not update the end to the inner interval's end, we update the larger one instead.
如果order by end, 那么[[2, 3], [1, 4]] 就不会通过。[2,3]排在 [1,4]前面，到[1,4]时候检测到有overlap, 只更新了end，start还是2。

class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        List<Interval> res = new ArrayList<>();
        if (intervals == null || intervals.size() == 0) {
            return res;
        }
        Collections.sort(intervals, (a,b) -> a.start - b.start);
        int start = intervals.get(0).start, end = intervals.get(0).end;
        for(int i = 1; i <intervals.size(); i++) {
            Interval cur = intervals.get(i);
            if (cur.start <= end) {
                end = Math.max(end, cur.end);
            } else {
                res.add(new Interval(start, end));
                start = cur.start;
                end = cur.end;
            }
        }
        res.add(new Interval(start, end));
        return res;
    }
}

Approach 2:
和meeting rooms II一样，用2个array。我个人倾向于这种方法，不用去纠结按start排序还是按end 排序。
这个方法中心思想是找interval之间的空隙。一个interval的end和他下一个的start比较。如果没有overlap，肯定比下一个start小。那么我们就可以得到之前的merged interval。这是一个观察规律，无论怎么overlap，空隙左右的end和start index之差是1.

上图的空隙两边是E2和S3.

class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        List<Interval> res = new ArrayList<>();
        if (intervals == null || intervals.size() == 0) {
            return res;
        }
        int len = intervals.size();
        int[] starts = new int[len];
        int[] ends = new int[len];
        for(int i = 0; i < len; i++) {
            starts[i] = intervals.get(i).start;
            ends[i] = intervals.get(i).end;
        }

        Arrays.sort(starts);
        Arrays.sort(ends);
        for (int i = 0, j = 0; i < len; i++) {
            if (i == len - 1 || ends[i] < starts[i+1]) {
                res.add(new Interval(starts[j], ends[i]));
                j = i + 1;
            }
        }
        return res;
    }
}