forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSeoya0512.py
More file actions
26 lines (23 loc) · 896 Bytes
/
Seoya0512.py
File metadata and controls
26 lines (23 loc) · 896 Bytes
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)
- newInterval을 삽입할 위치 탐색 O(N)
- Intervals 병합을 위해 for문으로 모든 구간을 순회 O(N)
- O(N) + O(N) = O(N)
Space Complexity : O(N)
- output 리스트에 모든 구간을 저장 O(N)
'''
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
idx = 0
while idx < len(intervals) and intervals[idx][0] < newInterval[0]:
idx +=1
intervals.insert(idx, newInterval) # newInterval을 삽입할 위치 탐색 (O(N))
# Intervals 병합
output = [intervals[0]]
for interval in intervals[1:]:
# 이전 구간과 겹치는 경우
if output[-1][1] >= interval[0]:
output[-1][1] = max(output[-1][1], interval[1])
else:
output.append(interval)
return output