56. 合并区间（高频题）

56. 合并区间

• 解题思路
• 代码

解题思路

是否有重叠区间的问题，直接贪心思路，根据数组的end或者start进行升序排序，再看看start和end的大小关系来判断是否重叠。像435题就是一样的类型。
不过本题要注意，一定要根据start的升序排列，不能根据end来排列，不然就会出现下图所示的情况：

代码

class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> arr = new ArrayList<int[]>();
        if (intervals.length == 0) {
            return new int[][]{};
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            //按照start升序排列
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        arr.add(intervals[0]);
        for (int i = 1; i < intervals.length; ++i) {
            //[x1,x2]和[y1,y2]比较，如果x2<y1说明这两个区间不相交
            if (arr.get(arr.size() - 1)[1] < intervals[i][0]) {
                arr.add(intervals[i]);
            }
            //否则，将这两个区间合并为 [x1,max(x2,y2)]，也就是新区间的end要保持最大
            else {
                arr.get(arr.size() - 1)[1] = Math.max(arr.get(arr.size() - 1)[1], intervals[i][1]);
            }
        }
        //为什么放0，0长度？可以看下源码就知道了
        return arr.toArray(new int[0][0]);
    }
}