56. Merge Intervals

56. Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

Example 1:

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.

My Solutions:

先按照start time排序，然后观察第i个的end time(last.end)和第i+1个的start time(curr.start)

1。如果last.end < curr.start, 把last加入结果

2。不然的话,把last变成 (last.start, max(last.end, curr.end))

记住最后一个last也要加入结果

class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals == null || intervals.size() <= 1) return intervals;
        
        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval a, Interval b) {
                return a.start - b.start;
            }
        });
        // 也可以这样写
        intervals.sort((i1, i2)-> {
            return Integer.compare(i1.start, i2.start);
        });
        
        List<Interval> list = new ArrayList<>();
        Interval last = intervals.get(0);
        for (int i = 1; i < intervals.size(); i++) {
            Interval curr = intervals.get(i);
            
            if (last.end < curr.start) { //interval is not continuous
                list.add(last);
                last = curr;
            } else {
                last.end = Math.max(last.end, curr.end);
            }
        }
        list.add(last);
        return list;                  
    }
}

如果input是int[][]，可以这样写

Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
// 或者
Arrays.sort(intervals, new Comparator<int[]>() {
    public int compare(int[] a, int[] b) {
        return Integer.compare(a[0], b[0]);
    }
});

ArrayList<int[]> 可以转化为二维int[][]

ArrayList<int[]> res = new ArrayList<>();
res.toArray(new int[res.size()][]);