LeetCode 435 Non-overlapping Intervals
概述
https://leetcode.com/problems/non-overlapping-intervals/
贪心法
首先我们需要对进行排序，否则的话我们在移除一个区间后，我们没办法轻松获知剩余区间是否依然有重叠。
https://labuladong.gitee.io/algo/3/27/104/
这道题是对后端点升序排序，我们保留后端点最小的，移除所有与其相交的（所有前端点大于其后端点的区间）， 之后寻找下一个最小后端点。
实际实现的时候，我们一次处理后面的区间，如果其不与上一个保留区间相交，则停止搜索与上一个保留区间相交的区间， 设当前区间为保留区间，开始新的搜索。这是因为，如果后面的区间想要与上一个保留区间相交，其开始端点必然先于上一个保留区间 的结束端点，进而导致其必然与当前保留区间相交。
所以是 O(n) 的时间复杂度，而非 O(n^2)。
对于后端点相同的区间要怎么处理呢？无所谓，不用特殊处理，首先这些区间留哪一个都可以， 因为对于后面的端点而言，看是否与之相交是看其后端点，所以这些区间对他们来说没有区别， 如果相交则哪一个都相交，否则哪一个都不相交。
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) -> bool {
return a[1] < b[1];
});
int count = 0;
int lastEnd = INT_MIN;
for (auto& i : intervals) {
if (i[0] < lastEnd) {
count ++;
} else {
lastEnd = i[1];
}
}
return count;
}
};
简单解释一下为什么这样做 okay。亦即，为什么我们要保留当前后端点最靠前的。因为选后端点最靠前的值，使得后续区间与之相交的 区间个数是最少的，因为后续区间判断是否与之相交看的就是后续区间的前端点是否先于改区间的后端点，那后端点越靠前， 则自然满足的越少。