435. 无重叠区间

435. 无重叠区间

有意思的题

1.dp

类似LIS，复杂度为

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& inter) {
        int n=inter.size();
        if(!n)return 0;

        sort(inter.begin(),inter.end(),[](const vector<int>&a,const vector<int>&b){
            if(a[0]!=b[0]) return a[0]<b[0];
            return a[1]<b[1];
        });

        int dp[n];

        for(int i=0;i<n;i++){
            dp[i]=1;
            for(int j=0;j<i;j++){
                if(inter[j][1]<=inter[i][0]){
                    dp[i]=max(dp[i],dp[j]+1);
                }
            }
        }
        int res=0;
        for(int i=0;i<n;i++)res=max(res,dp[i]);
        return n-res;
    }
};

2.贪心

复杂度为sort部分的
贪心部分复杂度为

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& inter) {
        int n=inter.size();
        if(!n)return 0;
        
        sort(inter.begin(),inter.end(),[](const vector<int>&a,const vector<int>&b){
            if(a[1]!=b[1]) return a[1]<b[1];
            return a[0]<b[0];
        });
        int right=inter[0][1];
        int res=1;
        for(int i=1;i<n;i++){
            if(inter[i][0]>=right){
                right=inter[i][1];
                res++;
            }
        }

        return n-res;
    }
};