贪心算法|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

理解后独自敲的代码，语法不熟练啊！

还有可笑的错误！