合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

解法一

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>(){
            @Override
            public int compare(int []o1, int []o2) {
                if (o1[0]==o2[0]){
                    return o1[1] - o2[1];
                }
                return o1[0] - o2[0];
            }
        });
        int n = intervals.length;
        int res[][] = new int[n][2];
        int index = -1;
        for (int i = 0;i<n;i++){
            //如果是第一个元素，获取第二个元素的第一位比当前res中的最后一位大的话，则直接加入
            if (index==-1 || intervals[i][0]>res[index][1]){
                ++index;
                res[index][0] = intervals[i][0];
                res[index][1] = intervals[i][1];
            }else {     
                res[index][1] = Math.max(intervals[i][1], res[index][1]);
            }
        }
        //复制指定长度的数组
        return Arrays.copyOf(res,index+1);
    }
}

解法二

class Solution {
    public static int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>(){
            @Override
            public int compare(int []o1, int []o2) {
                if (o1[0]==o2[0]){
                    return o1[1] - o2[1];
                }
                return o1[0] - o2[0];
            }
        });
        int n = intervals.length;
        int res[][] = new int[n][2];
        int index = 0;
        int start = intervals[0][0];
        int end = intervals[0][1];
        //下一个数组的起始值必须要小于上一个数组的最大值才能合并
        for (int i = 1;i<n;i++){
            //如果当前最小界比上一个的最大界小 说明可以合并 ，更新更新后的上界
            if (intervals[i][0]<=end){
                end = Math.max(intervals[i][1],end);
            }else {
                //说明不能继续合并了 ，把之前合并的结果存入结果集中
                res[index][0] = start;
                res[index][1] = end;
                index++;
                 //更新start 和 end 为当前新范围
                start = intervals[i][0];
                end = intervals[i][1];
            }
        }
        res[index][0] = start;
        res[index][1] = end;
        return Arrays.copyOf(res,index+1);
    }
}