程序员社区

LeetCode-56-合并区间

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

LeetCode-56-合并区间插图
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;
    }
}
LeetCode-56-合并区间插图1
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][]);
    }
}
LeetCode-56-合并区间插图2
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;
        
    }
}
赞(0) 打赏
未经允许不得转载:IDEA激活码 » LeetCode-56-合并区间

一个分享Java & Python知识的社区