代码实现起来比较简单,但是贪心的思想理解起来没那么容易,详细的介绍可以阅读贪心算法之区间调度问题
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
int ans=0;
if(intervals.size()==0) return 0;
sort(intervals.begin(),intervals.end(),comp);
vector<int> x = intervals[0];
for(int i = 1;i < intervals.size();i++)
{
if(intervals[i][0] < x[1])
ans++;
else
x = intervals[i];
}
return ans;
}
private:
static bool comp(const vector<int> &a,const vector<int>&b) {
return a[1] < b[1];
}
};
运行效率:
Runtime: 12 ms, faster than 96.24% of C++ online submissions for Non-overlapping Intervals.
Memory Usage: 10.2 MB, less than 91.50% of C++ online submissions for Non-overlapping Intervals.