LeetCode 435. Non-overlapping Intervals【區間貪心模闆題】⭐⭐⭐⭐⭐

文章目錄

• 題目描述
• 結果
• 實作
• • 碼前思考
  • 代碼實作
  • 碼後思考
• 二刷代碼

題目描述

結果

時間複雜度非常不好！！！

實作

碼前思考

1. 我是想用dp實作這個問題的，但是貌似最後應該選貪心的，(lll￢ω￢)，我跑了很多網友的代碼，發現dp大多超出了1000ms。
2. 主要是之前看了工作安排的題目，是以覺得這道題目跟工作安排很像。
3. 思路在下面

   

代碼實作

class Solution {
private:
    vector<int> dp;
public:
    static bool cmp(vector<int> a,vector<int> b){
        if(a[0]<=b[0]){
            return true;
        }else{
            return false;
        }
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int size = intervals.size();

        sort(intervals.begin(),intervals.end(),cmp);

        //遞推數組
        dp.assign(size,1);

        //進行遞推
        for(int i=0;i<size;i++){
            for(int j=0;j<i;j++){
                int li = intervals[i][0];
                int rj = intervals[j][1];
                if(li >= rj){
                    dp[i] = max(dp[i],dp[j]+1);
                }
            }
        }

        int ans = 0;

        for(int i=0;i<size;i++){
            ans = max(ans,dp[i]);
        }

        return size-ans;
    }
};
           

碼後思考

1. 之前我沒有 将所有區間按照起點的大小進行排序 ，導緻逾時了。。。因為一個一個比較起點和終點就是O(n2)的時間複雜度了，但是如果進行了排序，雖然不能保證區間前面一定是前驅，但是可以保證起點一定在前面！這裡需要記住，以後要進行排序。 代碼如下：

   for(int i=0;i<size;i++){
       for(int j=0;j<i;j++){
           int li = intervals[i][0];
           int rj = intervals[j][1];
           if(li >= rj){	//判斷到底是不是前驅
               dp[i] = max(dp[i],dp[j]+1);
           }
       }
   }
              

2. 這個問題其實也是一個 類LIS問題 ，前提是我們要對起點進行排序，一排序完畢，它就是一個LIS問題了，之前的LeetCode 1048. Longest String Chain也是需要自己進行排序轉換成LIS問題！
3. 對于類LIS問題，一個關鍵就是根據題目的意思，将子問題挪到原問題之前解決，常見的方式就是排序！上面兩道都是這麼做的！！！要記住了。
4. 另外，這道題也是DAG，之前想用DAG的，但是構造圖太費時間了，逾時了！是以還是直接用LIS解就行了！！！

二刷代碼

采用貪心的模闆進行求解：

class Solution {
public:
    static bool cmp(vector<int> a,vector<int> b){
        return a[1]<b[1];
    }

    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int len = intervals.size();
        if(len==0){
            return 0;
        }
        
        //首先對所有區間進行排序
        sort(intervals.begin(),intervals.end(),cmp);

        int maxv = 1;//至少一個區間
        int end = intervals[0][1];

        for(int i=1;i<len;i++){
            if(intervals[i][0]>=end){
                maxv++;
                end = intervals[i][1];
            }else{
                continue;
            }
        }

        return len-maxv;
    }
};