[ leetcode 문제풀이 ] Non-overlapping Intervals

Non-overlapping Intervals - LeetCode

Non-overlapping Intervals - LeetCode

(Non-overlapping Intervals 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

 

< Non-overlapping Intervals 문제 설명 >

 

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.

 

intervals[i]가 구간의 시작과 끝([starti, endi])을 나타내는 intervals 배열이 주어질 때, intervals가 non-overlapping이기 위해 삭제해야하는 interval의 최소 개수를 리턴하여라.

 

다음 세 가지 출력 예시가 주어졌다.

 

 

주어진 제한 조건은 다음과 같다:

1  ≤  intervals.length  ≤  10^5

intervals[i].length == 2

-5*10^4  ≤  starti  < endi  ≤ 5*10^4

 

 

 

---

< Non-overlapping Intervals 문제 접근 >

 

이 문제는 meeting room이라고 일컫는 문제와 같은 상황이다. 하나의 회의실이 있고 meeting schedule이 담긴 배열이 주어질 때 가장 많은 수의 회의를 진행할 수 있는 조합을 찾으라는 것이다. 이 문제는 greedy algorithm을 사용해 풀 수 있다.

 

greedy를 적용하는 방법은 interval을 선택하는 매 순간에 start가 가장 큰 interval을 선택하고 이와 중복되는 interval은 제외하는 것이다. 이 과정을 거듭해 선택된 interval의 모음이 바로 중복되는 interval을 최소한으로 삭제하는 non-overlapping interval이다.

이 알고리즘에서 조건(interval의 end가 중복되지 않는)을 만족하면서 start가 가장 큰 interval을 brute force하게 찾게 되면 O(n^2)의 복잡도를 가지게 되므로 interval을 미리 정렬해두어 찾는데 필요한 시간을 줄인다.

 

이 greedy 알고리즘의 정당성은 다음과 같이 보일 수 있다.  

 

1. s_late (: 가장 늦게 시작하는 interval)를 포함하는 최적해가 존재한다.

→ s_late를 포함하지 않는 최적해가 존재한다고 하자. 그러면 non-overlapping intervals에서 가장 마지막 interval을 삭제하고 s_late를 넣을 수 있다. (가장 마지막 interval보다 s_late의 interval 시작이 더 뒤이기 때문에 s_late를 넣어도 non-overlapping임) 따라서, 이 intervals 역시 최적해다.

2. 최적 부분 구조를 만족

→ s_late를 선택하고 s_late와 중복되는 interval을 삭제하였다고 하면, 남은 부분 문제는 intervals에서 중복되지 않도록 가장 많은 interval을 선택하는 것이므로 이는 초기 문제와 같다.

 

이를 바탕으로 작성한 코드는 다음과 같다. (Cpp 사용)

 

#include <algorithm>

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    int n = intervals.size();
    sort(intervals.begin(), intervals.end());
        
    int can_end = 123456, ans_cnt = 0;
    for(int i=n-1;i>-1;i--){
        if(intervals[i][1] <= can_end)
            can_end = intervals[i][0];
        else
            ans_cnt++;
    }
    return ans_cnt;
} // runtime : 505 ms (faster than 71.07 %), memory usage : 89.9 MB (less than 47.54 %)

 

문제에서는 삭제해야하는 interval의 수를 리턴하라 하였으므로 조건을 만족하지 않는 경우(=interval을 삭제해야하는 경우, interval이 중첩되는 경우) 리턴하는 ans_cnt를 1 증가한다. 한편, 조건을 만족하는 경우 해당 interval을 포함하는 것이므로 가능한 interval의 범위(=can_end)를 업데이트한다.

 

이렇게 intervals를 순회하며 계산된 ans_cnt는 바로 삭제해야하는 interval의 수가 된다.