56. 合并区间

难度中等930收藏分享切换为英文接收动态反馈

以数组 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] 可被视为重叠区间。

提示：

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

image-20210518092014003

class Solution {
    public static class Range {
        public int start;
        public int end;

        public Range(int s, int e) {
            start = s;
            end = e;
        }
    }

    public static class RangeComparator implements Comparator<Range> {

        @Override
        public int compare(Range o1, Range o2) {
            return o1.start - o2.start;
        }

    }

    // intervals  N * 2
    public static int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][0];
        }
        Range[] arr = new Range[intervals.length];
        for (int i = 0; i < intervals.length; i++) {
            arr[i] = new Range(intervals[i][0], intervals[i][1]);
        }
        Arrays.sort(arr, new RangeComparator());//第一步，通过比较器，让子数组以开始位置，从小到大排序
        ArrayList<Range> ans = new ArrayList<>();//返回的List
        int s = arr[0].start;
        int e = arr[0].end;
        for (int i = 1; i < arr.length; i++) {//核心逻辑
            if (arr[i].start > e) {//对比组的开始位置大于合并组的结束位置，重新调整合并组
                ans.add(new Range(s, e));
                s = arr[i].start;
                e = arr[i].end;
            } else {///对比组的开始位置小于合并组的结束位置 [1,3] [2,6]-->[1,6]
                e = Math.max(e, arr[i].end);
            }
        }
        ans.add(new Range(s, e));//收集答案，加入最后一组合并组
        return generateMatrix(ans);
    }

    public static int[][] generateMatrix(ArrayList<Range> list) {
        int[][] matrix = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            matrix[i] = new int[] { list.get(i).start, list.get(i).end };
        }
        return matrix;
    }
}

image-20210518092128951

class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> res = new ArrayList<>();
        if(intervals==null || intervals.length==0){
            return intervals;
        }
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0],b[0]));
        
        int start = intervals[0][0];
        int end = intervals[0][1];
        for(int[] x: intervals){
            if(x[0]<=end){
                end = Math.max(end,x[1]);
            }
            else{
                res.add(new int[]{start,end});
                start = x[0];
                end = x[1];
            }
        }
        res.add(new int[]{start,end});
        return res.toArray(new int[0][]);
    }
}

image-20210518094105181

执行用时为 1 ms 的范例

class Solution {
    public int[][] merge(int[][] intervals) {

        if (intervals.length <= 1) {
            return intervals;
        }

        int count = 0;
        for (int i = 0;i < intervals.length;i ++) {
            for (int j = i + 1;j < intervals.length;j ++) {
                if ((intervals[i][0] <= intervals[j][1]) && (intervals[i][1] >= intervals[j][0])) {//[1,3] [2,6]
                    if (intervals[i][0] <= intervals[j][0]) {
                        intervals[j][0] = intervals[i][0];
                    }
                    if (intervals[i][1] >= intervals[j][1]) {
                        intervals[j][1] = intervals[i][1];
                    }
                    count ++;
                    intervals[i] = null;//合并后，前面一组重置为null，输出的时候，直接跳过
                    break;
                }
            }
        }

        int[][] arrInt = new int[intervals.length-count][];
        for (int i = 0,j = 0;i < intervals.length;i ++) {
            if (intervals[i] != null) {
                arrInt[j++] = intervals[i];
            }
        }
        return arrInt;
        
    }
}