題目： LeetCode - 435. Non-overlapping Intervals

題目說明

給一個二維陣列代表區間，求需要刪除多少個區間使得區間中沒有交集。( 需要刪除最少的區間 )

解題思路

為了方便計算，我們先將區間依照右端點以小到大排序。接著選定一個區間，然後計算右邊的區間和目前區間交集的個數，這些都是需要刪除的區間，接著將目前區間換成目前找到不交集的區間，重複做此步驟即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    static bool cmp(const vector<int>& l, const vector<int>& r) { return l[1] < r[1]; }
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int count = 0, n = intervals.size(), l = 0, r;
        sort(intervals.begin(), intervals.end(), cmp);
        while(l < n)
        {
            r = l + 1;
            while(r < n && intervals[l][1] > intervals[r][0]) ++r;
            count += r - l - 1;
            l = r;
        }
        return count;
    }
};