56. 合并区间

1. 题目

给你一个 无重叠的 ，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例 1：

1
2
输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]

示例 2：

1
2
3
输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

示例 3：

1
2
输入：intervals = [], newInterval = [5,7]
输出：[[5,7]]

示例 4：

1
2
输入：intervals = [[1,5]], newInterval = [2,3]
输出：[[1,5]]

示例 5：

1
2
输入：intervals = [[1,5]], newInterval = [2,7]
输出：[[1,7]]

提示：

  • 0 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= intervals[i][0] <= intervals[i][1] <= 10^5
  • intervals 根据 intervals[i][0] 按 升序 排列
  • newInterval.length == 2
  • 0 <= newInterval[0] <= newInterval[1] <= 10^5

2. 思路

  • 本题的核心跟56. 合并区间是一致的，本质上都是将区间进行重新排序，因此一个简单的方式是将原有的intervals区间与新的newInterval进行合并，都置入一个List<int[]>中，随后再采用与56. 合并区间一致的排序算法即可得到答案
  • 另一种比较有意思的做法是将整个原有的区间与新的区间分为3段区间，目前根据题目已知的是
    • 原有区间不会重叠
    • 原有区间是有序的（按照区间的起始位置做了排序）
  • 可以将区间如下所示进行拆分，分别为左边部分（未重叠区间），与新区间重叠的中间部分，右边部分（未重叠区间）

image.png

图源：「手画图解」57. 插入区间 | 分成 3 个阶段考察

  • 整体代码切分为三个while循环遍历intervals区间，专注于处理各个部分
  • 首先处理的是左部分未重叠区间，当interval[1] < newInterval[0]时，可以直接加入至结果数组
  • 其次处理的是中间部分重叠区间，当newInterval[1] <= interval[0]时，可以在同一个数组位置判断获取最小的左区间以及最大的右区间（这一步体现了合并 & 插入）
  • 最后处理的是右部分未重叠区间，直接插入剩余的intervals区间

3. 代码

  • 合并区间 + 排序区间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        var allIntervals = new ArrayList<int[]>();

        allIntervals.add(newInterval);
        for (var interval : intervals) {
            allIntervals.add(interval);
        }

        Collections.sort(allIntervals, (i1, i2) -> i1[0] - i2[0]);

        var result = new int[allIntervals.size()][2];
        var idx = -1;

        for (var interval : allIntervals) {
            if (idx == -1 || result[idx][1] < interval[0]) {
                idx++;
                result[idx][0] = interval[0];
                result[idx][1] = interval[1];
            } else {
                result[idx][1] = Math.max(result[idx][1], interval[1]);
            }
        }

        return Arrays.copyOf(result, idx + 1);
    }
}
  • 三段式处理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        var result = new int[intervals.length + 1][2];
        var idx = 0;
        var i = 0;

        while (i < intervals.length && intervals[i][1] < newInterval[0]) {
            result[idx][0] = intervals[i][0];
            result[idx][1] = intervals[i][1];
            i++;
            idx++;
        }

        while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        result[idx] = newInterval;
        idx++;

        while (i < intervals.length) {
            result[idx][0] = intervals[i][0];
            result[idx][1] = intervals[i][1];
            i++;
            idx++;
        }

        return Arrays.copyOf(result, idx);
    }
}

4. 复杂度

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

image-20230906120013850