问题描述
给出一个无重叠的 ，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
示例 1：
输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]
示例 2：
输入：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] 重叠。
注意：输入类型已在 2019 年 4 月 15 日更改。请重置为默认代码定义以获取新的方法签名。
解题思路
需要考虑五种情况：
intervals 或 newInterval 为空newInterval 在 intervals 中的所有区间最前面且没有相交newInterval 在 intervals 中的所有区间最后面且没有相交newInterval 在 intervals 相邻的两个区间中间且与这两个区间没有相交newInterval 与 intervals 的一个或多个区间相交
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | class Solution:
def insert(
self, intervals: List[List[int]], newInterval: List[int]
) -> List[List[int]]:
# intervals 或 newInterval 为空
if not intervals or not newInterval:
return intervals + [newInterval]
# newInterval 在 intervals 中的所有区间最前面且没有相交
if newInterval[1] < intervals[0][0]:
return [newInterval] + intervals
# newInterval 在 intervals 中的所有区间最后面且没有相交
if newInterval[0] > intervals[-1][1]:
return intervals + [newInterval]
first = intervals[0]
if newInterval[0] > first[1]: # 新区间与第一个区间没有相交
return [first] + self.insert(intervals[1:], newInterval)
else: # 新区间与第一个区间相交
return self.insert(
intervals[1:],
[min(newInterval[0], first[0]), max(newInterval[1], first[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
32
33
34
35
36
37
38
39
40
41
42
43
44 | class Solution:
def insert(
self, intervals: List[List[int]], newInterval: List[int]
) -> List[List[int]]:
# intervals 或 newInterval 为空
if not intervals or not newInterval:
return intervals + [newInterval]
# newInterval 在 intervals 中的所有区间最前面且没有相交
if newInterval[1] < intervals[0][0]:
return [newInterval] + intervals
# newInterval 在 intervals 中的所有区间最后面且没有相交
if newInterval[0] > intervals[-1][1]:
return intervals + [newInterval]
left, right = -1, -1
for i, x in enumerate(intervals):
# newInterval 与 x 有相交
if not (newInterval[1] < x[0] or newInterval[0] > x[1]):
if left == -1:
left = i
right = i
# ### newInterval 与 x 无相交
# newInterval 刚好在 x 和 x 的上一个区间中间
elif newInterval[1] < x[0] and newInterval[0] > intervals[i - 1][1]:
return intervals[:i] + [newInterval] + intervals[i:]
# intervals 中与 newInterval 由有相交到没有相交的第一个区间
elif newInterval[1] < x[0]:
break
return (
intervals[:left]
+ [
[
min(intervals[left][0], newInterval[0]),
max(intervals[right][1], newInterval[1]),
]
]
+ intervals[right + 1 :]
)
|
后两种情况可以综合为一种情况考虑，即与 newInterval 最靠近但不相交的左右两个区间。
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 | class Solution:
def insert(
self, intervals: List[List[int]], newInterval: List[int]
) -> List[List[int]]:
# intervals 或 newInterval 为空
if not intervals or not newInterval:
return intervals + [newInterval]
# newInterval 在 intervals 中的所有区间最前面且没有相交
if newInterval[1] < intervals[0][0]:
return [newInterval] + intervals
# newInterval 在 intervals 中的所有区间最后面且没有相交
if newInterval[0] > intervals[-1][1]:
return intervals + [newInterval]
left, right = -1, len(intervals)
# 与 newInterval 最靠近但不相交的左右两个区间
for i, x in enumerate(intervals):
if newInterval[0] > x[1]:
left = i
elif newInterval[1] < x[0]:
right = i
break
return (
intervals[: left + 1]
+ [
[
min(intervals[left + 1][0], newInterval[0]),
max(intervals[right - 1][1], newInterval[1]),
]
]
+ intervals[right:]
)
|
在末尾添加多余的一项，将判断合并到同一个循环内。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | class Solution:
def insert(
self, intervals: List[List[int]], newInterval: List[int]
) -> List[List[int]]:
if not intervals or not newInterval:
return intervals + [newInterval]
ans = []
m = max(intervals[-1][1], newInterval[1]) + 1
intervals = intervals + [[m, m]]
for i, (l, r) in enumerate(intervals):
if newInterval[1] < l: # 必然会从这里退出
break
elif newInterval[0] > r:
ans.append([l, r])
else:
newInterval = [min(l, newInterval[0]), max(r, newInterval[1])]
return ans + [newInterval] + intervals[i:-1]
|
Warning
最后增加的一项可能在其它语言中导致数据溢出。