[LeetCode] 435. Non-overlapping Intervals

435. 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.

 

 

1. 문제 상황

주어진 구간에서 겹치는 구간을 최소화하려면 몇 개의 구간을 제거해야 하는지 묻는 문제.

겹치지 않는 구간의 최대 개수를 유지하려면 어떤 구간을 선택하는 게 좋을까?

 

2.문제의 특성과 제한사항

구간은 [start, end] 형태

겹치지 않는 구간끼리 최대한 많이 유지하려면 겹치지 않는 기준을 찾아야하고

구간이 겹친다면 하나를 반드시 제거해야 함

 

3. 예시

intervals = [[1, 2], [1, 3], 2, 3], [3, 4]]

에서, 종료시간이 짧은 구간을 먼저 선태갛는 게 유리함.

예를 들어 [1, 3] 대신 [1, 2]를 선택하면 더 많은 구간을 유지할 수 있음!

 

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        # 종료 시간을 기준으로 정렬
        intervals.sort(key=lambda x:x[1])

        result = 0
        # 종료 시간을 기억하는 변수에 -무한대로 초기화
        end = float('-inf')

        # 각 구간 순회
        for s, e in intervals:
            # 만약 시작 시간이 직전 종료 시간보다 작다면
            # 다음 시작 시간 < 직전 종료 시간이므로 겹침
            if s < end:
                result += 1
            # 그렇지 않을 경우엔 갱신
            else:
                end = e
        
        return result

 

4. 시간복잡도

정렬에 O(n logn) 이 필요

반복문 O(n)

총합 : O(n log n)