Leetcode - 435. Non-overlapping Intervals

문제

interval이 주어졌을때, 중첩이 발생하지 않도록 interval을 제거할때, 최소한으로 제거할 수 있는 갯수는?

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.

아이디어

• Gready
  두 interval이 가질 수 있는 세가지 경우의 수에 따라 각각 처리. Gready하게 O(n)에 계산이 가능해짐. 현재가 cur이고 그 다음 인터벌이 next 라고 할때, 아래와 같이 처리하면 된다. (해설 참고함)

case 1 
         ----   ---
         cur    next
case 2 : cur을 제거
         cur    --------x
         next      ---
case 3 : next를 제거
         cur    -----
         next     ------x

해결

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int cur = 0;
        int next = 1;
        int min_rm = 0;
        if (intervals.size() == 1)
            return min_rm;
        sort(intervals.begin(), intervals.end());
        
        while (next < intervals.size()) {
            // if case 1
            if (intervals[cur][1] <= intervals[next][0]) {
                cur = next; // <- cur will be next , not cur++
                next++;
            } else if (intervals[cur][1] >= intervals[next][1]) { // case 2
                min_rm++;
                cur = next; // <- cur will be next
                next++;
            } else { // case 3 
                min_rm++;
                next++;
            }
        }
        return min_rm;
    }
};