56.合并区间

以数组 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\le intervals.length\le {10}^4$
• $intervals[i].length==2$
• $0\le star{t}_i\le en{d}_i\le {10}^4$

解法一(排序)

思路分析

1. 对于若干个区间进行合并, 首先则需要确定如何判断两个区间需要合并, 即区间1的右边界大于等于区间2的左边界时,说明两个区间需要合并;
2. 解决判断两个区间合并问题后, 则需要确定如何合并更加方便;
3. 对于散列的若干个区间, 可以按照区间的左边界进行升序排序, 对于左边界相等则按照右边界进行升序排序, 如此散列的区间就变得有序, 可以很容易的判断当前区间是否需要与前一个区间进行合并;
4. 即当前区间左边界是否小于等于前一段已合并区间的右边界, 若小于,则重叠需要合并, 若不小于, 则从当前区间开始,继续寻找可以合并的区间;

实现代码

class Solution {
    public int[][] merge(int[][] intervals) {
        // 排序
        Arrays.sort(intervals, (i1, i2) -> {
            if (i1[0] == i2[0]) {
                return i1[1] - i2[1];
            } else {
                return i1[0] - i2[0];
            }
        });
        List<int[]> ans = new ArrayList<>();
        int left = intervals[0][0];     // 记录合并区间左
        int right = intervals[0][1];    // 记录合并区间右
        int n = intervals.length;
        for (int i = 0; i < n; ++ i) {
            if (intervals[i][0] <= right) {
                // 出现重叠区间 更新right
                right = Math.max(right, intervals[i][1]);
            } else {
                // 已有不重叠区间 将已合并区间加入结果中
                ans.add(new int[]{left, right});
                // 更新left和right
                left = intervals[i][0];
                right = intervals[i][1];
            }
            // 保证最后一个区间加入到结果集中
            if (i == n-1) {
                ans.add(new int[]{left, right});
            }
        }
        return ans.toArray(new int[ans.size()][]);  // 转化为二维数组输出
    }
}

运行结果

2024/10/08 15:24:34

解答成功:

执行耗时:7 ms,击败了90.30% 的Java用户

内存消耗:45.47 MB,击败了64.83% 的Java用户

复杂度分析

• 时间复杂度: 排序需要花费的时间复杂度为$O(nlo{g}^n)$, 遍历合并区间时间复杂度为 $O(n)$,因此总的复杂度为$O(nlo{g}^n)$
• 空间复杂度: 使用List列表对结果进行存储, 复杂度为$O(n)$