[DSA][Intervals] 03. Non-overlapping Intervals

LeetCode 435

 

03. Non-overlapping Intervals

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note that intervals which only touch at a point are non-overlapping. For example, [1, 2] and [2, 3] are non-overlapping.

 

 

[질문하기]

- 간격의 경계 값이 같은 경우는 겹치는 것으로 보나요? NO

- 입력 배열은 정렬되어 있나요? NO

 

[아이디어]

- 끝나는 시간이 빠를수록 다음 구간과 겹칠 확률이 낮아지므로 구간을 끝나는 시점 기준으로 정렬해서, 더 많은 구간을 선택할 수 있도록 한다.

 

 

[풀이 1] Greedy (Sort By End)

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key = lambda pair: pair[1])
        res = 0
        prevEnd = intervals[0][1]
        
        for start, end in intervals[1:]:
            if prevEnd > start:
                res += 1
            else:
                prevEnd = end
        
        return res

겹치는 구간을 최소로 제거하려면, 겹치지 않는 구간을 최대한 많이 선택하는 것이 중요하다.

이를 위해 구간을 끝나는 시간이 빠른 순서로 정렬하고, 각 구간의 시작 시간이 이전 구간의 끝나는 시간보다 작으면 겹치는 구간이므로 제거한다. 겹치지 않는 경우에는 해당 구간을 선택하고, 이전 구간 정보를 업데이트해 나간다.

 

 

⏱️ 시간복잡도

구간을 정렬한 뒤 한 번 순회하므로, 전체 시간 복잡도는 O(nlogn)이다.

🧠 공간복잡도

추가적인 자료구조를 사용하지 않고, 구간과 개수를 저장하는 변수만 사용하므로 공간 복잡도는 O(1)이다.