문제

• 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

결과