435. 無重疊區間 -力扣（leetCode）c++貪心算法

1. 無重疊區間

   給定一個區間的集合，找到需要移除區間的最小數量，使剩餘區間互不重疊。

注意:

可以認為區間的終點總是大于它的起點。

區間 [1,2] 和 [2,3] 的邊界互相“接觸”，但沒有互相重疊。

示例 1:

輸入: [ [1,2], [2,3], [3,4], [1,3] ]

輸出: 1

解釋: 移除 [1,3] 後，剩下的區間沒有重疊。

示例 2:

輸入: [ [1,2], [1,2], [1,2] ]

輸出: 2

解釋: 你需要移除兩個 [1,2] 來使剩下的區間沒有重疊。

示例 3:

輸入: [ [1,2], [2,3] ]

輸出: 0

解釋: 你不需要移除任何區間，因為它們已經是無重疊的了。

分析：最小數量，也是一道貪心算法的題目，目标是找出重疊區間數量，如果區間1-2後，來一個4-6，又來一個3-5，無疑會對計算造成負擔，因為我們貌似隻能用i*j的數量級去每個區間往後周遊看i區間的區間尾部是否會比j的區間頭部大，大的話就重疊。

考慮到上述會比較麻煩，雖然也可以解出，但我們可以通過先對每個區間尾部大小進行排序，區間按尾部大小排好序後，從左往右周遊時不斷判定是否重疊即可。

代碼如下（含代碼注釋）：

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(),intervals.end(), [](vector<int>a1,vector<int>a2){return a1[1]<a2[1];
    });//按照區間尾部大小的關鍵字進行排序
        int count=0,i,pre;
        pre=intervals[0][1];

        for(i=1;i<intervals.size();i++)
        {
            if(intervals[i][0]<pre)//如果後面的區間開頭比前面記錄的區間尾部pre要小，說明區間重疊
                count++;
            else
            {
                pre=intervals[i][1];//區間沒重疊，pre變為更大的區間的尾部
            }
        }
        return count;

    }
};
           

覺得該篇文章有用的請不要忘記忘記點選右下角的大拇指~

歡迎大家關注我的公衆号：Smooth前端成長記錄

公衆号同步更新CSDN部落格内容，想友善閱讀部落格的C友可以來關注我的公衆号以便獲得更優良的閱讀體驗~