435.non-overlapping-intervals 无重叠区间

问题描述

435.无重叠区间

解题思路

本题和452.用最少数量的箭引爆气球可以说解题思路一模一样，区间数减去452.用最少数量的箭引爆气球就可以说是本题要求的答案，但是要注意的是，在本题中，区间端点相同是不认为重叠的。

代码

class Solution {
  private:
    static bool cmp(vector<int> &a, vector<int> &b) {
        if (a[0] == b[0])
            return a[1] < b[1];
        return a[0] < b[0];
    }

  public:
    int eraseOverlapIntervals(vector<vector<int>> &intervals) {
        std::sort(intervals.begin(), intervals.end(), cmp);
        int cnt = 1;
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] >= intervals[i - 1][1])
                cnt++;
            else {
                intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]);
            }
        }
        return intervals.size() - cnt;
    }
};