forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathseungriyou.py
More file actions
41 lines (33 loc) · 1.29 KB
/
seungriyou.py
File metadata and controls
41 lines (33 loc) · 1.29 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
# https://leetcode.com/problems/insert-interval/
from typing import List
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
"""
[Complexity]
- TC: O(n)
- SC: O(n)
[Approach]
intervals의 각 interval에 대해 다음의 케이스로 나눠볼 수 있다.
1) left에 해당하는 interval: left에 추가
2) right에 해당하는 interval: right에 추가
3) newInterval과 겹치는 interval: ns & ne 업데이트 (newInterval 확장)
"""
ns, ne = newInterval
# left: end < ns
# right: start > ne
left, right = [], []
for s, e in intervals:
# 1) left에 해당하는 interval이라면, left에 추가
if e < ns:
left.append([s, e])
# 2) right에 해당하는 interval이라면, right에 추가
elif s > ne:
right.append([s, e])
# 3) newInterval과 겹치는 interval이라면, ns & ne 업데이트
else:
ns = min(ns, s)
ne = max(ne, e)
# left.append([ns, ne])
# left.extend(right)
# return left
return left + [[ns, ne]] + right