435. 无重叠区间 -力扣（leetCode）c++贪心算法_c++ 无重叠区间

435. 无重叠区间
     给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:
可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

示例 1:
输入: [ [1,2], [2,3], [3,4], [1,3] ]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:
输入: [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:
输入: [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

分析：最小数量，也是一道贪心算法的题目，目标是找出重叠区间数量，如果区间1-2后，来一个4-6，又来一个3-5，无疑会对计算造成负担，因为我们貌似只能用i*j的数量级去每个区间往后遍历看i区间的区间尾部是否会比j的区间头部大，大的话就重叠。
考虑到上述会比较麻烦，虽然也可以解出，但我们可以通过先对每个区间尾部大小进行排序，区间按尾部大小排好序后，从左往右遍历时不断判定是否重叠即可。

代码如下（含代码注释）：

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(),intervals.end(), [](vector<int>a1,vector<int>a2){return a1[1]<a2[1];
    });//按照区间尾部大小的关键字进行排序
        int count=0,i,pre;
        pre=intervals[0][1];

        for(i=1;i<intervals.size();i++)
        {
            if(intervals[i][0]<pre)//如果后面的区间开头比前面记录的区间尾部pre要小，说明区间重叠
                count++;
            else
            {
                pre=intervals[i][1];//区间没重叠，pre变为更大的区间的尾部
            }
        }
        return count;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

觉得该篇文章有用的请不要忘记忘记点击右下角的大拇指~

欢迎大家关注我的公众号：Smooth前端成长记录
公众号同步更新CSDN博客内容，想方便阅读博客的C友可以来关注我的公众号以便获得更优良的阅读体验~