无重叠区间

题目描述

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

输入输出样例

 &emps;输入是一个数组，数组由多个长度固定为2的数组组成，表示区间的开始和结尾。输出一个整数，表示需要移除的区间数量。

Input: [[1,2], [2,4], [1,3]]
Output: 1

  在这个样例中，我们可以移除区间[1,3],使得剩余的区间[[1,2],[2,4]]互不重叠。 # 题解   在选择要保留区间时，区间的结尾十分重要：选择的区间结尾越小，余留给其它区间的空间就越大，就越能保留更多的区间。因此，我们采取的贪心策略为：优先保留结尾小且不相交的区间。   具体实现方法为，先把区间按照结尾的大小进行增序排序，每次选择结尾最小且和前一个选择的区间不重叠的区间。我们这里使用C++的Lambda,结合std::sort()函数进行自定义排序。   在样例中，排序后的数组为[[1,2],[1,3],[2,4]].按照我们的贪心策略，首先初始化为区间[1,2];由于[1,3]与[1,2]相交，我们跳过该区间；由于[2,4]与[1,2]不相交，我们将其保留。因此最终保留的区间为[[1,2],[2,4]]。

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;
        int n = intervals.size();
        
        sort(intervals.begin(),intervals.end(),[&](vector<int> A,vector<int> B){return A[1] < B[1];});
        
        int total = 0,prev = intervals[0][1];
        for (int i = 1; i < n; i++) {
            if (intervals[i][0] < prev) 
                ++total;
            else 
                prev = intervals[i][1];
        }
        return total;
    }
};