Posted on 2023-01-16 16:42
Uriel 阅读(38)
评论(0) 编辑 收藏 引用 所属分类:
模拟 、
闲来无事重切Leet Code 、
大水题
给定一堆数值区间intervals，要加入一个新的区间newInterval，求更新后的数值区间list
因为intervals是已经排好序的，所以只要O(n)扫一遍intervals，每次对比intervals[i]的起点终点与newInterval的范围，根据不同情况更新合并后的区间塞入ans，注意考虑intervals为空的情况
代码写得比较烂，但速度和内存表现还可以
1 #57
2 #Runtime: 47 ms (Beats 98.92%)
3 #Memory: 16.7 MB (Beats 94.85%)
4
5 class Solution(object):
6 def insert(self, intervals, newInterval):
7 """
8 :type intervals: List[List[int]]
9 :type newInterval: List[int]
10 :rtype: List[List[int]]
11 """
12 ans = []
13 i = 0
14 fg = 0
15 while i < len(intervals) :
16 if intervals[i][0] > newInterval[1]:
17 if not fg:
18 ans.append([newInterval[0], newInterval[1]])
19 fg = 1
20 ans.append([intervals[i][0], intervals[i][1]])
21 i += 1
22 continue
23 if intervals[i][1] < newInterval[0]:
24 ans.append([intervals[i][0], intervals[i][1]])
25 i += 1
26 continue
27 p1 = min(newInterval[0], intervals[i][0])
28 while i < len(intervals) and intervals[i][1] < newInterval[1]:
29 i += 1
30 if i == len(intervals):
31 p2 = newInterval[1]
32 ans.append([p1, p2])
33 fg = 1
34 else:
35 if intervals[i][0] > newInterval[1]:
36 p2 = newInterval[1]
37 ans.append([p1, p2])
38 ans.append([intervals[i][0], intervals[i][1]])
39 else:
40 p2 = intervals[i][1]
41 ans.append([p1, p2])
42 fg = 1
43 i += 1
44 continue
45 if not fg:
46 ans.append([newInterval[0], newInterval[1]])
47 return ans