0057. 插入区间【中等】
1. 📝 题目描述
给你一个无重叠的,按照区间起始端点排序的区间列表 intervals,其中 intervals[i] = [start_i, end_i] 表示第 i 个区间的开始和结束,并且 intervals 按照 start_i 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。
在 intervals 中插入区间 newInterval,使得 intervals 依然按照 start_i 升序排列,且区间之间不重叠(如果有必要的话,可以合并区间)。
返回插入之后的 intervals。
注意你不需要原地修改 intervals。你可以创建一个新数组然后返回它。
示例 1:
输入:intervals = [[1, 3], [6, 9]], newInterval = [2, 5]
输出:[[1, 5], [6, 9]]1
2
2
- 示例 2:
输入:intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], newInterval = [4, 8]
输出:[[1, 2], [3, 10], [12, 16]]1
2
2
解释:这是因为新的区间 [4, 8] 与 [3, 5], [6, 7], [8, 10] 重叠。
提示:
0 <= intervals.length <= 10^4intervals[i].length == 20 <= start_i <= end_i <= 10^5intervals根据start_i按升序排列newInterval.length == 20 <= start <= end <= 10^5
2. 🎯 s.1 - 一次遍历(三阶段合并)
c
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume
* caller calls free().
*/
int** insert(int** intervals, int intervalsSize, int* intervalsColSize,
int* newInterval, int newIntervalSize, int* returnSize,
int** returnColumnSizes) {
int** result = (int**)malloc(sizeof(int*) * (intervalsSize + 1));
*returnColumnSizes = (int*)malloc(sizeof(int) * (intervalsSize + 1));
int idx = 0, i = 0;
// 添加所有在 newInterval 左侧不重叠的区间
while (i < intervalsSize && intervals[i][1] < newInterval[0]) {
result[idx] = (int*)malloc(sizeof(int) * 2);
result[idx][0] = intervals[i][0];
result[idx][1] = intervals[i][1];
(*returnColumnSizes)[idx] = 2;
idx++;
i++;
}
// 合并所有与 newInterval 重叠的区间
while (i < intervalsSize && intervals[i][0] <= newInterval[1]) {
if (intervals[i][0] < newInterval[0])
newInterval[0] = intervals[i][0];
if (intervals[i][1] > newInterval[1])
newInterval[1] = intervals[i][1];
i++;
}
result[idx] = (int*)malloc(sizeof(int) * 2);
result[idx][0] = newInterval[0];
result[idx][1] = newInterval[1];
(*returnColumnSizes)[idx] = 2;
idx++;
// 添加所有在 newInterval 右侧不重叠的区间
while (i < intervalsSize) {
result[idx] = (int*)malloc(sizeof(int) * 2);
result[idx][0] = intervals[i][0];
result[idx][1] = intervals[i][1];
(*returnColumnSizes)[idx] = 2;
idx++;
i++;
}
*returnSize = idx;
return result;
}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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
js
/**
* @param {number[][]} intervals
* @param {number[]} newInterval
* @return {number[][]}
*/
var insert = function (intervals, newInterval) {
const result = []
let i = 0
// 添加所有在 newInterval 左侧不重叠的区间
while (i < intervals.length && intervals[i][1] < newInterval[0]) {
result.push(intervals[i])
i++
}
// 合并所有与 newInterval 重叠的区间
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.push(newInterval)
// 添加所有在 newInterval 右侧不重叠的区间
while (i < intervals.length) {
result.push(intervals[i])
i++
}
return result
}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
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
py
class Solution:
def insert(
self, intervals: List[List[int]], newInterval: List[int]
) -> List[List[int]]:
result = []
i = 0
# 添加所有在 newInterval 左侧不重叠的区间
while i < len(intervals) and intervals[i][1] < newInterval[0]:
result.append(intervals[i])
i += 1
# 合并所有与 newInterval 重叠的区间
while i < len(intervals) and intervals[i][0] <= newInterval[1]:
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
i += 1
result.append(newInterval)
# 添加所有在 newInterval 右侧不重叠的区间
while i < len(intervals):
result.append(intervals[i])
i += 1
return result1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
- 时间复杂度:
,其中 n 是区间数组的长度,只需遍历一次 - 空间复杂度:
,不计输出数组,只使用常数额外空间
算法思路:
- 将区间分为三组,依次处理:
- 第一段 => 左侧不重叠:所有
end < newInterval[0]的区间,直接加入结果 - 第二段 => 重叠合并:所有
start <= newInterval[1]的区间,与newInterval合并(取min(start)和max(end)),合并完成后将newInterval加入结果 - 第三段 => 右侧不重叠:剩余区间直接加入结果