Leetcode-56-合并区间（区间调度）

一、题目

给出一个区间的集合，请合并所有重叠的区间。

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

https://leetcode-cn.com/problems/merge-intervals/

二、解题思路

整体思路

先对左区间进行排序，如果第一个区间的右区间 < 第二个区间的左区间，则直接添加；如果 >= 的话，则合并，左区间不变，右区间取两者最大值

关键问题

答案结果是二维数组，个数不确定时，如何初始化？
方法1、申请和原数组一样的长度（最多个数），然后return时候截取

int[][] res = new int[intervals.length][2];
int idx = -1;     // idx计数
return Arrays.copyOf(res, idx + 1);

方法2、申请动态数组初始化，然后转array

List<int[]> res = new ArrayList<>();
return res.toArray(new int[0][]);

new int[0][]表示不指定行、行自动填充，如果为new int[4][], 即使结果为[[1,6],[8,10],[15,18]]，也会强制输出[[1,6],[8,10],[15,18],null]，即不足行null补充

注1：排序

按照第一个数值升序

Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);

lambda 表达式，定义了一个comparator对象，当参数传进去
或者

Arrays.sort(intervals, new Comparator<int[]>(){
    public int compare(int[] a, int[] b){
        return a[0] - b[0];
    }
});

或者

Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));

注2：

// 先判断是否为空，再能取长度
if (intervals == null || intervals.length == 0 || intervals.length == 1) {
    return intervals;
}

三、题解

暴力解法

题解1:

Java题解

class Solution {
    public int[][] merge(int[][] intervals) {
        // 先判断是否为空，再能取长度
        if (intervals == null || intervals.length == 0 || intervals.length == 1) {
            return intervals;
        }
        Arrays.sort(intervals, new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                return a[0] - b[0];
            }
        });
        // 如何申请一个不确定个数的二维数组
        // int[][] res = new int[intervals.length][2];      // 方法1
        List<int[]> res = new ArrayList<>();        // 方法2
        int left = intervals[0][0];
        int right = intervals[0][1];
        for (int[] invs : intervals) {
            if (invs[0] <= right) {
                right = Math.max(right, invs[1]);
            }else {
                res.add(new int[]{left, right});       // 方法2
                left = invs[0];
                right = invs[1];
            }
        }
        res.add(new int[]{left, right});            // 最后一个，容易漏掉
        // return res.toArray(new int[res.size()][]);   // 区别？
        return res.toArray(new int[0][]);
    }
}

结果

执行用时：7 ms, 在所有 Java 提交中击败了92.33%的用户
内存消耗：42.7 MB, 在所有 Java 提交中击败了17.48%的用户

参考

1、题解参考
2、优秀题解
https://leetcode-cn.com/problems/merge-intervals/solution/chi-jing-ran-yi-yan-miao-dong-by-sweetiee/

https://leetcode-cn.com/problems/merge-intervals/solution/pai-xu-by-powcai/

https://leetcode-cn.com/problems/merge-intervals/solution/tan-xin-suan-fa-java-by-liweiwei1419-3/

最后编辑于：2020.08.23 15:52:15