forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathdusunax.py
More file actions
60 lines (50 loc) · 2.02 KB
/
dusunax.py
File metadata and controls
60 lines (50 loc) · 2.02 KB
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
'''
# 57. Insert Interval
## A. insert first, merge later
- use binary search to find the index of the new interval.(bisect_left)
- insert the new interval into the list.
- iterate through the list and merge the intervals.
## B. insert, merge, insert
- inserting the intervals into the result list until finding the correct index of the new interval.
- merge the overlapping intervals than insert the newInterval into the result list.
- insert the remaining intervals into the result list.
'''
class Solution:
'''
# A. insert first, merge later
- TC: O(n)
- SC: O(n)
'''
def insertUsingBisectLeftToFindIndex(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
start_idx = bisect_left([interval[0] for interval in intervals], newInterval[0]) # TC: O(log n)
intervals.insert(start_idx, newInterval) # TC: O(n)
result = [] # SC: O(n)
for interval in intervals: # TC: O(n)
if not result or result[-1][1] < interval[0]:
result.append(interval)
else:
result[-1][1] = max(result[-1][1], interval[1])
return result
'''
# B. insert, merge, insert
- TC: O(n)
- SC: O(n)
'''
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
result = [] # SC: O(n)
i = 0
n = len(intervals)
# 1. insert until finding the correct index of newInterval
while i < n and intervals[i][1] < newInterval[0]: # TC: O(n)
result.append(intervals[i])
i += 1
# merge overapping intervals & insert newInterval
while i < n and intervals[i][0] <= newInterval[1]: # TC: O(n)
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
i += 1
result.append(newInterval)
while i < n: # TC: O(n)
result.append(intervals[i])
i += 1
return result