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 considered overlapping.
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Solution

解法比较straight forward,排序然后merge即可

注意点:
二维数组如何排序

Complexity

O(N) O(N)

Code

class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals == null || intervals.length == 0) return new int[0][2];
        Arrays.sort(intervals, new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                return a[0] - b[0];
            }
        });
        List<int[]> list = new ArrayList<>();
        
        for(int[] interval : intervals){
            if(list.size() == 0)
                list.add(interval);
            else{
                int[] lastInterval = list.get(list.size() - 1);
                if(interval[0] <= lastInterval[1])
                    lastInterval[1] = Math.max(lastInterval[1], interval[1]);
                else
                    list.add(interval);
            }
        }
        
        int[][] res = new int[list.size()][2];
        for(int i = 0; i < list.size(); i++)
            res[i] = list.get(i);
        return res;
    }
}