Interval, Scheduling 문제 (LeetCode 435)

문제 설명

 Interval을 Scheduling 하는 문제는 코딩 문제의 대표적인 유형 중 하나이다. 예를 들어, 시계열을 기준으로 시작 시간과 종료 시간이 주어진 여러개의 수업이 있을 때, 이를 최대한 많이 수강할 수 있는 수업들을 Scheduling 하는 것이다. 이 문제는 Sorting과 Greedy Algorithm 개념을 활용해 풀 수 있다.

 

 먼저 Scheduling 문제는 Greedy Algorithm을 적용할 수 있다. 이를 적용하기 위해서는 2가지를 고려해야 하는데, 첫번째는 각 Interval이 Sorting 되어야 한다는 것이다. 그리고 Interval의 종료 시간을 기준으로 Sorting 되어야 한다.

 

문제 예시

 4개 수업의 시작 시간 및 종료 시간이 다음과 같이 주어졌을 때, 겹치지 않고 수강할 수 있는 최대 수업의 개수는 무엇인가? (이는, 겹치지 않고 최대로 수업을 수강하기 위해 몇개의 수업을 삭제해야 하는가? 로도 물어볼 수 있다.)

Class = [[1, 2], [2, 3], [3, 4], [1, 3]];
첫번째 인덱스 : 시작 시간, 두번째 인덱스 : 종료 시간

 

Step 1 : Greedy Algorithm을 적용하기 위해, 먼저 각 Class의 Interval을 종료 시간을 기준으로 Ascending으로 정렬한다. 종료 시간이 같은 Interval은 시작 시간을 기준으로 Ascending 정렬한다.

Class = [[1, 2], [2, 3], [3, 4], [1, 3]];
Sorted Class = [[1, 2], [1, 3], [2, 3], [3, 4]]; // Ascending with 2nd idx

 

Step 2 : 첫번째 Interval 부터 순차적으로 접근한다. 접근한 Interval의 시작 시간이 앞 Interval의 종료 시간보다 이후인지 확인한다. 그렇다면 넘어가고, 그렇지 않으면 삭제해준다. 해당 Interval은 앞 Interval과 Overlap되기 때문이다. (Greedy Algorithm 개념이 적용된다.) 위 예시에서는 [1, 3] Interval의 시작 시간이 1인데, 앞 Interval [1, 2]의 종료 시간보다 이전이므로 Overlap 된다. 따라서 삭제한다. 위 과정을 반복해주면 Overlap 되지 않는 Interval을 최대로 가지는 배열이 완성된다.

Non Overlap Intervals = [[1, 2], [2, 3], [3, 4]];

 

필요 알고리즘

 이러한 문제는 Interval이 주어졌을 때 Overlap 되지 않도록 Scheduling 하는 문제로 분류할 수 있다. 문제를 풀기 위해서는 Sorting, Greedy Algorithm 개념에 대한 이해가 필요하다. 문제를 풀어보고 싶으면 Leet Code 435. Non-overlapping Intervals 문제를 참고하자. 

https://leetcode.com/problems/non-overlapping-intervals/description/?envType=study-plan-v2&envId=leetcode-75 

Non-overlapping Intervals - LeetCode

 

위 문제를 푼 코드는 다음과 같다. Sorting 함수를 사용하기 위해 <Algorithm> 헤더를 추가했고, 종료 시간을 기준으로 정렬하기 위해 cmp 함수를 정의하였다.

bool cmp(vector<int>& vector1, vector<int>& vector2)
{
    bool RetVal = true;

    if (vector1[1] == vector2[1]){
        RetVal = vector1[0] < vector2[0];
    }
    else{
        RetVal = vector1[1] < vector2[1];
    }

    return RetVal;
}

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int PrevEnd = 0;
        int NumOfErase = 0;

        // Ascending Sort of end time
        sort(intervals.begin(), intervals.end(), cmp);

        PrevEnd = intervals[0][1];

        for (int i = 1; i < intervals.size(); ++i){
            if (intervals[i][0] >= PrevEnd){
                PrevEnd = intervals[i][1];
            }
            else{
                ++NumOfErase;
            }
        }

        return NumOfErase;
    }
};