插入区间
与上篇的合并区间类似,插入区间的描述是:
给你一个 无重叠的 ,按照区间起始端点排序的区间列表 intervals
,其中 intervals[i] = [starti, endi]
表示第 i
个区间的开始和结束,并且 intervals
按照 starti
升序排列。同样给定一个区间 newInterval = [start, end]
表示另一个区间的开始和结束。
举个例子:
示例 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] 重叠。
解决方法:
(1)与上篇的合并区间类似,先将增加的区间放在list最后,然后进行排序,最后进行遍历,下面是代码:
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
intervals.extend([newInterval])
intervals.sort(key=lambda p:p[0])
ans_list=[]
for in_i in intervals:
if ans_list and ans_list[-1][1]>=in_i[0]:
ans_list[-1][1]=max(ans_list[-1][1],in_i[1])
else:
ans_list.append(in_i)
return ans_list
但是上述的代码,没有考虑原有数组的有序性,重新排序太耗时了,后面有机会再看看怎么进行优化了。