【LeetCode75】第七十二题 无重叠区间

目录

题目：

示例：

分析：

代码：

---

题目：

示例：

分析：

题目给我们一个二维数组，里面的每个数组都表示一段区间，我们可以删除任意区间，问我们最少需要删除多少区间才可以使所有区间都不重叠。

我们这题因为要删除最少的区间，因此我们需要用到贪心的思想。

我们如何判断两个区间有重叠呢，如果一个区间的左端大于另一个区间的左端并且小于其右端，那么就是有重叠了。

为了更好的判断是否重叠，首先我们先对区间排序，以区间的左端点升序来排。这样，我们依次比较相邻端点的左右端即可知道是否有重叠。

那么问题就在于当两个区间重叠的时候，我们应该删除哪个区间才能使得利益最大化。

我们遍历全部区间，用一个变量记录已经遍历过的区间的最右端。

每当有区间的左端小于这个最右端时，我们就需要移除一个区间了，具体是移除哪一个呢，我们不需要知道，我们只知道我们这个最右端越小，那么下次需要移除的概率就越小，因此我们只需要判断，当前的区间的右端如果比最右端更小，那么我们就更新最右端为较小的值。

这样我们就能保证下一次更不容易需要移除区间。

代码：

class Solution {
public:
    int eraseOverlapIntervals(vectorint>>& intervals) {
        if(intervals.size()<=1) return 0;
        //按照左端排序
        sort(intervals.begin(),intervals.end(),[](vector<int>&a,vector<int>&b){return a[0]0];});
        int res=0;
        int end=intervals[0][1];    //贪心,仅更新最短右端
        for(int i=1;isize();i++){
            if(intervals[i][0]>=end){
                end=intervals[i][1];
            }else{
                res++;
                end=min(end,intervals[i][1]);
            }
        }
        return res;
    }
};