贪心算法

区间问题

给定多个区间，计算让这些区间互不重叠所需要移除区间的最少个数。起止相连不算重叠。

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.

class Solution {
 public:
  int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    int n = intervals.size();
    // 按照结尾从小到大排序
    // 比较函数使用了lambda表达式
    sort(
        intervals.begin(), intervals.end(),
        [](const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; });

    // 第一个肯定被选中
    int ans = 1, prev = intervals[0][1];
    
    for (int i = 1; i < n; ++i) {
      if (intervals[i][0] >= prev) {
        ++ans;
        prev = intervals[i][1];
      }
    }

    return n - ans;
  }
};