[[438794]]

無重疊區(qū)間

力扣題目鏈接：https://leetcode-cn.com/problems/non-overlapping-intervals

給定一個(gè)區(qū)間的集合，找到需要移除區(qū)間的最小數(shù)量，使剩余區(qū)間互不重疊。

注意: 可以認(rèn)為區(qū)間的終點(diǎn)總是大于它的起點(diǎn)。區(qū)間 [1,2] 和 [2,3] 的邊界相互“接觸”，但沒有相互重疊。

示例 1:

• 輸入: [ [1,2], [2,3], [3,4], [1,3] ]
• 輸出: 1
• 解釋: 移除 [1,3] 后，剩下的區(qū)間沒有重疊。

示例 2:

• 輸入: [ [1,2], [1,2], [1,2] ]
• 輸出: 2
• 解釋: 你需要移除兩個(gè) [1,2] 來使剩下的區(qū)間沒有重疊。

示例 3:

• 輸入: [ [1,2], [2,3] ]
• 輸出: 0
• 解釋: 你不需要移除任何區(qū)間，因?yàn)樗鼈円呀?jīng)是無重疊的了。

思路

相信很多同學(xué)看到這道題目都冥冥之中感覺要排序，但是究竟是按照右邊界排序，還是按照左邊界排序呢?

這其實(shí)是一個(gè)難點(diǎn)!

按照右邊界排序，就要從左向右遍歷，因?yàn)橛疫吔缭叫≡胶?，只要右邊界越小，留給下一個(gè)區(qū)間的空間就越大，所以從左向右遍歷，優(yōu)先選右邊界小的。

按照左邊界排序，就要從右向左遍歷，因?yàn)樽筮吔鐢?shù)值越大越好(越靠右)，這樣就給前一個(gè)區(qū)間的空間就越大，所以可以從右向左遍歷。

如果按照左邊界排序，還從左向右遍歷的話，其實(shí)也可以，邏輯會(huì)有所不同。

一些同學(xué)做這道題目可能真的去模擬去重復(fù)區(qū)間的行為，這是比較麻煩的，還要去刪除區(qū)間。

題目只是要求移除區(qū)間的個(gè)數(shù)，沒有必要去真實(shí)的模擬刪除區(qū)間!

我來按照右邊界排序，從左向右記錄非交叉區(qū)間的個(gè)數(shù)。最后用區(qū)間總數(shù)減去非交叉區(qū)間的個(gè)數(shù)就是需要移除的區(qū)間個(gè)數(shù)了。

此時(shí)問題就是要求非交叉區(qū)間的最大個(gè)數(shù)。

右邊界排序之后，局部最優(yōu)：優(yōu)先選右邊界小的區(qū)間，所以從左向右遍歷，留給下一個(gè)區(qū)間的空間大一些，從而盡量避免交叉。全局最優(yōu)：選取最多的非交叉區(qū)間。

局部最優(yōu)推出全局最優(yōu)，試試貪心!

這里記錄非交叉區(qū)間的個(gè)數(shù)還是有技巧的，如圖：

無重疊區(qū)間

區(qū)間，1，2，3，4，5，6都按照右邊界排好序。

每次取非交叉區(qū)間的時(shí)候，都是可右邊界最小的來做分割點(diǎn)(這樣留給下一個(gè)區(qū)間的空間就越大)，所以第一條分割線就是區(qū)間1結(jié)束的位置。

接下來就是找大于區(qū)間1結(jié)束位置的區(qū)間，是從區(qū)間4開始。那有同學(xué)問了為什么不從區(qū)間5開始?別忘已經(jīng)是按照右邊界排序的了。

區(qū)間4結(jié)束之后，在找到區(qū)間6，所以一共記錄非交叉區(qū)間的個(gè)數(shù)是三個(gè)。

總共區(qū)間個(gè)數(shù)為6，減去非交叉區(qū)間的個(gè)數(shù)3。移除區(qū)間的最小數(shù)量就是3。

C++代碼如下：

class Solution { 
public: 
    // 按照區(qū)間右邊界排序 
    static bool cmp (const vector<int>& a, const vector<int>& b) { 
        return a[1] < b[1]; 
    } 
    int eraseOverlapIntervals(vector<vector<int>>& intervals) { 
        if (intervals.size() == 0) return 0; 
        sort(intervals.begin(), intervals.end(), cmp); 
        int count = 1; // 記錄非交叉區(qū)間的個(gè)數(shù) 
        int end = intervals[0][1]; // 記錄區(qū)間分割點(diǎn) 
        for (int i = 1; i < intervals.size(); i++) { 
            if (end <= intervals[i][0]) { 
                end = intervals[i][1]; 
                count++; 
            } 
        } 
        return intervals.size() - count; 
    } 
}; 

• 時(shí)間復(fù)雜度：O(nlogn) ，有一個(gè)快排
• 空間復(fù)雜度：O(1)

大家此時(shí)會(huì)發(fā)現(xiàn)如此復(fù)雜的一個(gè)問題，代碼實(shí)現(xiàn)卻這么簡單!

總結(jié)

本題我認(rèn)為難度級(jí)別可以算是hard級(jí)別的!

總結(jié)如下難點(diǎn)：

• 難點(diǎn)一：一看題就有感覺需要排序，但究竟怎么排序，按左邊界排還是右邊界排。
• 難點(diǎn)二：排完序之后如何遍歷，如果沒有分析好遍歷順序，那么排序就沒有意義了。
• 難點(diǎn)三：直接求重復(fù)的區(qū)間是復(fù)雜的，轉(zhuǎn)而求最大非重復(fù)區(qū)間個(gè)數(shù)。
• 難點(diǎn)四：求最大非重復(fù)區(qū)間個(gè)數(shù)時(shí)，需要一個(gè)分割點(diǎn)來做標(biāo)記。

這四個(gè)難點(diǎn)都不好想，但任何一個(gè)沒想到位，這道題就解不了。

一些錄友可能看網(wǎng)上的題解代碼很簡單，照葫蘆畫瓢稀里糊涂的就過了，但是其題解可能并沒有把問題難點(diǎn)講清楚，然后自己再?zèng)]有鉆研的話，那么一道貪心經(jīng)典區(qū)間問題就這么浪費(fèi)掉了。

貪心就是這樣，代碼有時(shí)候很簡單(不是指代碼短，而是邏輯簡單)，但想法是真的難!

這和動(dòng)態(tài)規(guī)劃還不一樣，動(dòng)規(guī)的代碼有個(gè)遞推公式，可能就看不懂了，而貪心往往是直白的代碼，但想法讀不懂，哈哈。

所以我把本題的難點(diǎn)也一一列出，幫大家不僅代碼看的懂，想法也理解的透徹!

補(bǔ)充

本題其實(shí)和452.用最少數(shù)量的箭引爆氣球非常像，弓箭的數(shù)量就相當(dāng)于是非交叉區(qū)間的數(shù)量，只要把弓箭那道題目代碼里射爆氣球的判斷條件加個(gè)等號(hào)(認(rèn)為[0，1][1，2]不是相鄰區(qū)間)，然后用總區(qū)間數(shù)減去弓箭數(shù)量 就是要移除的區(qū)間數(shù)量了。

把452.用最少數(shù)量的箭引爆氣球代碼稍做修改，就可以AC本題。

class Solution { 
public: 
    // 按照區(qū)間右邊界排序 
    static bool cmp (const vector<int>& a, const vector<int>& b) { 
        return a[1] < b[1]; 
    } 
    int eraseOverlapIntervals(vector<vector<int>>& intervals) { 
        if (intervals.size() == 0) return 0; 
        sort(intervals.begin(), intervals.end(), cmp); 
 
        int result = 1; // points 不為空至少需要一支箭 
        for (int i = 1; i < intervals.size(); i++) { 
            if (intervals[i][0] >= intervals[i - 1][1]) { 
                result++; // 需要一支箭 
            } 
            else {  // 氣球i和氣球i-1挨著 
                intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]); // 更新重疊氣球最小右邊界 
            } 
        } 
        return intervals.size() - result; 
    } 
}; 

這里按照 左區(qū)間遍歷，或者按照右邊界遍歷，都可以AC，具體原因我還沒有仔細(xì)看，后面有空再補(bǔ)充。

class Solution { 
public: 
    // 按照區(qū)間左邊界排序 
    static bool cmp (const vector<int>& a, const vector<int>& b) { 
        return a[0] < b[0]; 
    } 
    int eraseOverlapIntervals(vector<vector<int>>& intervals) { 
        if (intervals.size() == 0) return 0; 
        sort(intervals.begin(), intervals.end(), cmp); 
 
        int result = 1; // points 不為空至少需要一支箭 
        for (int i = 1; i < intervals.size(); i++) { 
            if (intervals[i][0] >= intervals[i - 1][1]) { 
                result++; // 需要一支箭 
            } 
            else {  // 氣球i和氣球i-1挨著 
                intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]); // 更新重疊氣球最小右邊界 
            } 
        } 
        return intervals.size() - result; 
    } 
}; 

本文轉(zhuǎn)載自微信公眾號(hào)「代碼隨想錄」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系代碼隨想錄公眾號(hào)。