[區間問題] 最大不相交區間數量(區間問題+貪心)

文章目錄

• • 0. 前言
  • 1. 區間問題+貪心

0. 前言

玄學的貪心問題，一般全憑直覺。

貪心問題沒有固定讨論，沒有模闆，見多了就好了，證明想法的正确性是很困難的，大多采用反證法。

區間問題無非左端點、右端點、左右端點排序…

1. 區間問題+貪心

908. 最大不相交區間數量

本題和 [區間問題] 區間選點(區間問題+貪心) 一模一樣，一份代碼交兩遍就行了。貪心思路和證明思路都一緻，簡單對問題轉化即可。

貪心思路：

• 區間按右端點從小到大排序
• 從前往後依次枚舉每個區間
  • 如果目前區間中已經包含點，則直接跳過該區間
  • 否則，選擇目前區間的右端點

證明：

• 假設最優解為

  ans

  個不相交區間，以上述貪心思路選出來的區間為

  cnt

  個。即證明

  ans = cnt

  ，等價于

  ans >= cnt && ans <= cnt

• 首先，以上述貪心思路選擇出的

  cnt

  個區間，是一組可行方案。其覆寫了所有區間，滿足題目要求。且

  ans

  表示的是所有可行方案的最大值，那麼

  ans >= cnt

  成立
• 證明

  ans <= cnt

  時，可以采用反證法。假設

  ans > cnt

  ，則說明最多有

  ans

  個兩兩不交的區間，則至少需要

  ans

  個點才能将這些區間全部覆寫，然而實際上隻需要

  cnt

  個點就能覆寫全部區間，且

  cnt < ans

  。則沖突，故

  ans <= cnt

  成立
• 時間複雜度： O ( n l o g n ) O(nlogn) O(nlogn)

為什麼最大不相交區間數==最少覆寫區間點數呢？

• 因為如果幾個區間能被同一個點覆寫，說明他們相交了
• 是以有幾個點就是有幾個不相交區間。兩個問題的本質是等價的

代碼：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5+5;

struct Range {
    int l, r;
    bool operator<(const Range &W) const {
        return r < W.r;
    }
}range[N];

int main() {
    int n;
    cin >> n;
    
    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        range[i] = {a, b};
    }
    
    sort(range, range + n);
    
    int res = 0, ed = -2e9;
    for (int i = 0; i < n; ++i) 
        if (ed < range[i].l)
            ++res, ed = range[i].r;
    
    cout << res << endl;
    
    return 0;
}