[LeetCode 75] Medium - 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.

 

Example 1:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

Example 2:

Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.

Example 3:

Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

 

Constraints:

• 1 <= intervals.length <= 105
• intervals[i].length == 2
• -5 * 104 <= starti < endi <= 5 * 104

이 문제는 **주어진 interval 배열(intervals)**에서 겹치는 구간을 제거하여 나머지 구간들이 겹치지 않도록(non-overlapping) 만드는 최소한의 구간 개수를 구하는 문제입니다.

 

풀이 방법

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        # Step 1: intervals 리스트를 끝나는 시간(x[1]) 기준으로 오름차순 정렬합니다.
        # 정렬 후, 끝나는 시간이 빠른 구간부터 처리합니다.
        # 왜 끝나는 시간 기준으로 정렬하나요?
        # - 끝나는 시간이 빠른 구간을 선택하면 이후에 겹치는 구간을 최소화할 가능성이 높기 때문입니다.
        # 예: intervals = [[1,3],[2,4],[3,5]] → 끝나는 시간 기준으로 정렬 → [[1,3],[2,4],[3,5]]
        intervals.sort(key=lambda x: x[1])
        
        # Step 2: 초기화
        # prev_end는 이전에 선택된 구간의 끝나는 시간을 저장합니다.
        # 초기값으로 -inf를 설정하여 첫 번째 구간과 항상 겹치지 않도록 보장합니다.
        prev_end = float('-inf')  
        
        # remove_count는 겹치는 구간을 제거한 횟수를 저장합니다.
        remove_count = 0  

        # Step 3: 모든 구간을 순회하며 겹치는지 확인합니다.
        for start, end in intervals:
            # 현재 구간의 시작점(start)이 이전 선택된 구간의 끝점(prev_end)보다 크거나 같으면 두 구간은 겹치지 않습니다.
            if start >= prev_end:  
                # 현재 구간을 선택하고 prev_end를 현재 구간의 끝점으로 업데이트합니다.
                prev_end = end  
            else:  
                # 현재 구간의 시작점이 이전 구간의 끝점보다 작다면 두 구간이 겹칩니다.
                # 따라서 현재 구간을 제거하고 제거 횟수를 1 증가시킵니다.
                remove_count += 1  
                # 왜 제거할까요?
                # - 끝나는 시간이 더 빠른 구간(prev_end)을 유지하면 이후 구간과의 겹침을 줄일 가능성이 높기 때문입니다.
                # - prev_end는 업데이트하지 않습니다(기존 선택된 구간을 유지합니다).

        # Step 4: 제거된 구간의 총 개수를 반환합니다.
        return remove_count

 

https://youtu.be/nONCGxWoUfM?si=77-kUfjYRH_FldB0

 

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        # Step 1: intervals 배열을 `시작 시간` 기준으로 정렬
        # 예를 들어, intervals = [[1,3], [2,4], [3,5]]으로 정렬됨
        intervals.sort()
        
        # Step 2: 결과를 저장할 변수 초기화
        res = 0  # 제거해야 하는 구간의 수
        # prevEnd는 이전에 선택된 구간의 끝점을 저장
        prevEnd = intervals[0][1]  # 첫 번째 구간의 끝점으로 초기화
        
        # Step 3: 두 번째 구간부터 순회
        for start, end in intervals[1:]: 
            # 현재 구간의 시작점(start)과 이전 구간의 끝점(prevEnd)을 비교            
            if start >= prevEnd:  # 현재 구간이 이전 구간과 겹치지 않는 경우
                # 현재 구간을 선택하므로 prevEnd를 현재 구간의 끝점(end)으로 업데이트
                prevEnd = end
            else:  # 현재 구간이 이전 구간과 겹치는 경우
                # 현재 구간의 시작점(start)이 이전 구간의 끝점(prevEnd)보다 작다면 두 구간은 겹침
                # 이 경우, 겹치는 구간 중 하나를 제거해야 함
                res += 1  # 제거한 구간 수를 1 증가
                
                # 겹치는 구간들 중 끝나는 시간이 더 빠른 구간을 선택해야,
                # 이후 구간들이 더 많이 겹치지 않을 가능성이 높음
                # 즉, `더 빨리 끝나는 구간`을 선택하여 이후 겹침을 최소화
                # 이전 구간의 끝점(prevEnd)와 현재 구간의 끝점(end) 중 더 작은 값을 선택
                prevEnd = min(end, prevEnd)
        
        # Step 4: 제거한 구간 수 반환
        return res

 

이 코드와 GPT 코드의 차이

1. 정렬 기준:
   • 내 코드: 끝나는 시간 기준으로 정렬
   • 이 코드: 시작 시간 기준으로 정렬
2. prevEnd 업데이트 방식:
   • 내 코드: 겹치는 경우 prevEnd를 건드리지 않음.
   • 이 코드: 겹치는 경우 prevEnd를 **min(end, prevEnd)**로 업데이트.

---

결론

• 두 방법 모두 올바르게 동작하지만, 이 코드에서는 시작 시간 기준으로 정렬 후 겹침을 해결합니다. 
• 끝나는 시간 기준으로 정렬하는 방식이 직관적일 수 있지만, 두 방식 모두 효율적이고 결과는 동일합니다.
• GPT 코드가 좀 더 빠름

-----------------------------------------------------------------------------------------------------------------------------

 

두번째 시도

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

        # 2. 겹치지 않는 구간의 개수와 이전 구간 끝점 초기화
        non_overlap_count = 0
        prev_end = float('-inf')

        # 3. 구간 순회
        for start, end in intervals:
            # 현재 구간이 이전 구간과 겹치지 않는 경우
            if start >= prev_end:
                non_overlap_count += 1
                prev_end = end  # 현재 구간을 선택
            # 겹치는 경우: 현재 구간은 선택하지 않음 (그리디 선택)

        # 4. 전체 구간 수 - 겹치지 않는 구간 수
        return len(intervals) - non_overlap_count

 

최종 코드

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        # end 기준으로 오름차순 정렬
        intervals.sort(key=lambda x : x[1])
        overlap_cnt = 0
        prev_end = -float("inf")

        for start, end in intervals:
            if prev_end <= start:
                prev_end = end
            else:
                overlap_cnt+=1

        return overlap_cnt