本文主要是介绍贪心算法|435.无重叠区间，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
力扣题目链接
class Solution {
public:// 按照区间右边界排序static bool cmp (const vector<int>& a, const vector<int>& b) {return a[1] < b[1];}int eraseOverlapIntervals(vector<vector<int>>& intervals) {if (intervals.size() == 0) return 0;sort(intervals.begin(), intervals.end(), cmp);int count = 1; // 记录非交叉区间的个数int end = intervals[0][1]; // 记录区间分割点for (int i = 1; i < intervals.size(); i++) {if (end <= intervals[i][0]) {end = intervals[i][1];count++;}}return intervals.size() - count;}
};写算法题是需要集中注意力，静下心用心去写的。
如果你浮躁的话会发现理解不了，你如果静下心一步一步去画理清自己思路其实还是很容易的。
代码随想录 (programmercarl.com)
思路
相信很多同学看到这道题目都冥冥之中感觉要排序，但是究竟是按照右边界排序，还是按照左边界排序呢？
其实都可以。主要就是为了让区间尽可能的重叠。
我来按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。
此时问题就是要求非交叉区间的最大个数。
这里记录非交叉区间的个数还是有技巧的，如图：
区间，1，2，3，4，5，6都按照右边界排好序。
当确定区间 1 和 区间2 重叠后，如何确定是否与 区间3 也重贴呢？
就是取 区间1 和 区间2 右边界的最小值，因为这个最小值之前的部分一定是 区间1 和区间2 的重合部分，如果这个最小值也触达到区间3，那么说明 区间 1，2，3都是重合的。
接下来就是找大于区间1结束位置的区间，是从区间4开始。那有同学问了为什么不从区间5开始？别忘了已经是按照右边界排序的了。
区间4结束之后，再找到区间6，所以一共记录非交叉区间的个数是三个。
总共区间个数为6，减去非交叉区间的个数3。移除区间的最小数量就是3。
自己的理解：
刚开始一直静不下心去写，然后有些地方看不懂。
后来自己去看视频静下心去理解，梳理自己的思路。
卡哥视频讲的是按左区间排序，但是这个代码答案是右区间排序哦！
而且计算的count还是不重叠部分的。
1.注意i是从1开始，这样才能和前面的有所比较
2.判断区间是否重叠
上一个区间的右区间 <= 当前区间的左区间 （不重叠）
else 重叠
因为计算的是不重叠的count
所以不重叠count++
更改end
理解后独自敲的代码，语法不熟练啊！
还有可笑的错误！
这篇关于贪心算法|435.无重叠区间的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
