没啥好说的,贪心算法中最简单的题,《算法设计与分析》教科书中贪心章节的第一道典例
class Solution {
private:
static bool cmp(const vector<int>& a, const vector<int>& b) {
return a[1] < b[1];
}
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if (intervals.empty()) return 0;
sort(intervals.begin(), intervals.end(), cmp);
int count = 0;
int end = intervals[0][1];
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i][0] < end)
count++;
else end = intervals[i][1];
}
return count;
}
};