Description Link to heading

435.non-overlapping-intervals

Solution Link to heading

This problem is almost the same with 452.minimum-number-of-arrows-to-burst-balloons, the number intervals minus the result of 452.minimum-number-of-arrows-to-burst-balloons is the result of this problem.

Attention, [1, 3], [3, 5] is not overlapping intervals in this problem.

Code Link to heading 

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;
    }
};