Non-overlapping Intervals
문제
- non-overlap 되도록 최소한의 수의 interval 제거
- 몇개 제거하면 가능한가.
풀이
- 아 interval 문제 너무 어렵다..............
- start 순으로 sort
- 비교하면서, 겹쳐지면 더 뒤에까지 영향 주는 구간을 제거
- greedy 방식
from collections import deque
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort()
intervals = deque(intervals)
count = 0
while intervals:
pre = intervals.popleft()
if intervals:
post = intervals.popleft()
else:
break
if pre[1] > post[0]:
# overlapped
# 더 뒤에까지 영향을 주는 interval 제거
if pre[1] < post[1]:
# post를 제거
intervals.appendleft(pre)
count += 1
else:
# pre를 제거
intervals.appendleft(post)
count += 1
else:
# 겹쳐지지 않음. post는 뒤의 구간과 비교 위해서 다시 추가
intervals.appendleft(post)
return count
결과
- 아 interval 문제 너무 어렵다..............
- start 순으로 sort
- 비교하면서, 겹쳐지면 더 뒤에까지 영향 주는 구간을 제거
- greedy 방식
from collections import deque
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort()
intervals = deque(intervals)
count = 0
while intervals:
pre = intervals.popleft()
if intervals:
post = intervals.popleft()
else:
break
if pre[1] > post[0]:
# overlapped
# 더 뒤에까지 영향을 주는 interval 제거
if pre[1] < post[1]:
# post를 제거
intervals.appendleft(pre)
count += 1
else:
# pre를 제거
intervals.appendleft(post)
count += 1
else:
# 겹쳐지지 않음. post는 뒤의 구간과 비교 위해서 다시 추가
intervals.appendleft(post)
return count
결과
Author And Source
이 문제에 관하여(Non-overlapping Intervals), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@twinklesu914/Non-overlapping-Intervals저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)