Posted on 2023-01-16 16:42
Uriel 閱讀(59)
評論(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