题目描述
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
算法1
(区间合并) $O(n)$
额 之前;
分号忘删了 竟然python3也run过了。。。
c++のpush_back
和py的.append()
好像功能一致,至少对于数列来说
1. 对于新区间左边和右边的、与新区间没有重叠的区间,直接将它们按顺序插入;
2. 对于与新区间相交的区间,我们维护合并后区间的左端点和右端点,最后再将合并后的区间插入适当的位置。
时间复杂度分析:每个区间只会遍历一次,所以总时间复杂度是 $O(n)$.
Python 代码
class Solution:
def insert(self, a: List[List[int]], b: List[int]) -> List[List[int]]:
res = []
k = 0
while (k < len(a) and a[k][1] < b[0]):
res.append(a[k])
k+=1
if k< len(a):
b[0] = min(b[0], a[k][0])
while (k < len(a) and a[k][0] <= b[1]):
b[1] = max(b[1], a[k][1])
k += 1
res.append(b)
while (k < len(a)):
res.append(a[k])
k += 1
return res