435无重叠区间

目录

原题

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.empty())
            return 0;
        sort(intervals.begin(),intervals.end(),[](vector<int> a, vector<int> b){
            return a[0] < b[0];
        });
        sort(intervals.begin(), intervals.end(), [](vector<int> a, vector<int> b){
            return a[1] < b[1];
        });       // 将区间按后一个排序
//        for(int i = 0;i < intervals.size();i++)
//            cout<<intervals[i][0]<<intervals[i][1]<<endl;
        int total = 0, prev = intervals[0][1];
        for(int i = 1;i < intervals.size(); i++){
            if(prev > intervals[i][0])
                total++;
            else{
                prev = intervals[i][1];

            }
        }
        return total;

    }
};
int main(){
    Solution solution;
    int result;
    vector<vector<int> > intervals = {{1,2},{2,3},{3,4},{1,3}};
    result = solution.eraseOverlapIntervals(intervals);
    cout<<result<<endl;
    return result;
}

思路

先把所有区间按头尾最小排序,再从前面向后找不重复的区间,

问题

不知道为什么不把头排序也能解决问题,测试数据里没有第一个不是1的例子吗

上一篇:50-10-010-配置-整体配置


下一篇:js创建对象的三种方式和js工厂模式创建对象