forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathyolophg.py
More file actions
26 lines (22 loc) · 1.12 KB
/
yolophg.py
File metadata and controls
26 lines (22 loc) · 1.12 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
# Time Complexity: O(N) - iterate through the intervals once.
# Space Complexity: O(N) - store the merged intervals in a new list.
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
output = []
start, end = newInterval
for interval in intervals:
if interval[1] < start:
# no overlap, and the current interval ends before newInterval starts
output.append(interval)
elif interval[0] > end:
# no overlap, and the current interval starts after newInterval ends
output.append([start, end]) # insert merged interval before appending the remaining ones
output.extend(intervals[intervals.index(interval):]) # append remaining intervals
return output
else:
# overlapping case: merge intervals
start = min(start, interval[0])
end = max(end, interval[1])
# add the merged interval at the end if it wasn't added earlier
output.append([start, end])
return output