leetcode435.无重叠区间（中等）

属于区间问题的第二类题。 思路一：贪心 实现细节：按照右端点从小到大排序。

class Solution {
          
   
public:
    static bool cmp(const vector<int>& v1, const vector<int>& v2){
          
   
        return v1[1] < v2[1];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
          
   

        int n = intervals.size();
        sort(intervals.begin(), intervals.end(), cmp);
        int r = INT_MIN, ans = 0;
        for (auto& each : intervals) {
          
   
            if (each[0] >= r) {
          
   
                ans++;
                r = each[1];
            }
        }
        return n - ans;
    }
};

方法二：dp（超时，通不过，只用来拓展思路） 题目等价为：不重叠找出最多的区间 具体思路：先按照左端点/右端点升序排列。 dp[i]表示以v[i]结尾最多的区间个数。 转移方程：dp[i]=dp[j]+1 (0<=j<i且v[j].second <= v[i].first) 复杂度达到O(n^2)太高了，超时。。。。

class Solution {
          
   
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
          
   

        int n = intervals.size();
        vector<int> dp(n, 1);
        vector<pair<int, int>> v;
        sort(intervals.begin(), intervals.end());
        for (auto& each : intervals) {
          
   
            v.push_back({
          
   each[0], each[1]});
        }
        for (int i = 1; i < n; ++i) {
          
   
            for (int j = 0; j < i; ++j) {
          
   
                if (v[j].second <= v[i].first) dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        return n - dp[n - 1];
    }
};