[LC] 435. Non-overlapping Intervals #116
Description
어렵다.. ㅠ
Approach
Idea 1: Sorting & Greedy (Monotonic Stack)
각 interval의 시작과 끝 시각을 [s, e]라고 하자.
이때, 항상 빠른 e를 골라야지만 가장 적은 수의 interval을 제거하여 non-overlapping intervals를 남길 수 있다.
이는 빠른 e를 가진 interval을 남겨야 다른 intervals를 더 많이 수용할 수 있기 때문이다.
따라서 주어진 intervals를 e 기준으로 오름차순 정렬한 후 순회하면서
- 현재 보고 있는 interval을
[s, e]라고 하고, - 지금까지 남긴 intervals의
e중 가장 큰 값(= 가장 최근에 남긴 interval의e)을end라고 두자.
이때, end의 값과 현재 보고 있는 interval의 start s를 비교하여 다음과 같이 판단한다.
-
s < end: overlap 상황(1) 현재 보고 있는 interval이 가장 최근에 남긴 interval과 겹치고 (2)
end <= e이므로 (오름차순 정렬) 현재 보고 있는 interval은 제거 (cnt++) -
s >= end: non-overlap 상황가장 최근에 남긴 interval과 겹치지 않으므로 제거하지 않고,
end를e로 업데이트
Idea 2: Sorting & DP & Binary Search 📌
current interval을 유지할지(keep) 지울지(remove)를 결정하기 위해서 future intervals를 고려해야 한다는 점에서 DP를 적용할 수 있다.
따라서 intervals를 start 기준으로 오름차순 정렬한 후, 마지막 interval부터 순회하며 확인해나가는 것이 포인트이다!
Caution
➡️ intervals를 정렬했으므로 값이 아닌 idx로 접근해야 함에 주의!
n = len(intervals)
# intervals를 start 기준으로 오름차순 정렬
intervals.sort(key=lambda x: x[0])
# dp[i] = sorted intervals에서 index i 이후에 위치한 intervals가 non-overlapping이 되도록
# 제거해야 하는 intervals의 minimum 개수
# i == n일 때는 out of bound이므로, dp[n] = 0가 되도록 하기 위해 * (n + 1)
dp = [0] * (n + 1)이때, 각 iteration에서는 current interval 이후 첫 번째로 등장하는 next non-overlapping interval을 찾아야 한다!
이를 O(logn)에 수행하기 위해 binary search를 적용한 함수로 작성하면 다음과 같다.
def find_lower_bound(idx):
"""
intervals에서
(1) target(= current interval의 end) 이후에 start를 가지고 있으면서
(2) 가장 빠른
interval의 index를 찾는 함수
"""
curr_end = intervals[idx][1]
lo, hi = idx + 1, n
while lo < hi:
mid = lo + (hi - lo) // 2
if intervals[mid][0] < curr_end:
lo = mid + 1
else:
hi = mid
return lo또한, 각 iteration에서는 (1) current interval를 keep 하는 경우와 (2) current interval을 remove 하는 경우 중, 어떤 값이 더 작은 dp 값을 가지는지를 판단하여 DP table을 업데이트 한다.
# intervals를 뒤에서부터 확인
for idx in range(n - 1, -1, -1):
# current interval 다음에 위치하는 "첫 non-overlapping interval"을 찾음
# 즉, current interval을 keep 한 다음에 선택할 next interval의 index를 얻음
next_idx = find_lower_bound(idx)
# (1) keep current interval
# - dp[next_idx] = next non-overlapping interval의 dp 값
# - (next_idx - idx - 1) = current interval과 next non-overlapping interval 사이에 위치한
# overlapping intervals의 개수 (current interval을 택한다면 overlap 될 intervals 제외하기)
v1 = dp[next_idx] + (next_idx - idx - 1)
# (2) remove current interval
v2 = dp[idx + 1] + 1
# update dp table
dp[idx] = min(v1, v2)이렇게 구한 DP table에서 dp[0] 값을 반환하면 된다.
Complexity
- Time:
O(nlogn)(sorting 때문) - Space:
O(n)