最大不想交区间个数的类似问题,按照右端点升序排序,使用贪心算法;
重点是贪心算法的证明,也就是
greedy <= ans && greedy >= ans
==> greedy = ans 的情况
C++ 代码
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
// 右端点升序排序
auto cmp = [](const vector<int>& a, const vector<int>& b) {
return a[1] < b[1];
};
sort(intervals.begin(), intervals.end(), cmp);
int cnt = 1;
int ed = intervals[0][1];
// 贪心算法,不断添加区间,计算最大不重叠区间的个数
for(int i=1; i<intervals.size(); ++i){
vector<int> tmp = intervals[i];
if(tmp[0] >= ed) {
ed = tmp[1];
cnt++;
}
}
return intervals.size() - cnt;
}
};