區間覆蓋問題

一、問題描述

區間覆蓋問題是指，給定一些區間，選出最少的區間，使其可以完全覆蓋另一個給定的區間。例如，在給定區間[1,3],[2,4],[3,5],[4,6],[5,7]中，選擇[2,4],[4,6]即可覆蓋[1,5]這個區間。這是一個經典的NP難問題，因此需要尋找高效的演算法。

二、樸素貪心演算法

最直接的想法是貪心，選擇可以覆蓋最多區間的區間，一直重複該過程直到所有區間都被覆蓋。具體實現時，每次選擇左端點最靠左的區間，並且右端點最遠的區間作為當前可選的區間中最優的。當所有區間被覆蓋時結束演算法。以下是該演算法的代碼實現：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct Interval {
    int start;
    int end;
};

bool cmp(Interval& a, Interval& b) {
    if (a.start != b.start) {
        return a.start  b.end;
}

int main() {
    vector<Interval> intervals = { {1,3},{2,4},{3,5},{4,6},{5,7} };
    sort(intervals.begin(), intervals.end(), cmp);
    int n = intervals.size();
    int cnt = 0, idx = 0, maxRight = 0;
    while (idx < n && maxRight < intervals[n - 1].end) {
        int maxRightTmp = maxRight;
        while (idx < n && intervals[idx].start <= maxRightTmp) {
            maxRight = max(maxRight, intervals[idx].end);
            idx++;
        }
        cnt++;
    }
    cout << cnt << endl;
    return 0;
}

三、證明貪心演算法正確性

該演算法確保了每一步選擇的區間，都是覆蓋區間花費最小的區間之一。可以證明，該貪心演算法是正確的。

設S是所有被選出的區間的集合。假設存在更優的區間覆蓋方案T，令T中最左邊的區間為I，即T可以按照左端點從小到大的順序依次命名為I1，I2，…，Ik，其中I1是T中左端點最小的區間。將S中所有區間左端點小於等於I1的區間刪除，同理將T中I1的過右端點的所有區間刪除。此時，S和T中還剩下的所有區間仍然構成區間覆蓋問題，且仍然可以先按左端點從小到大排序，然後將左端點小於等於最優區間的區間刪除。每一步操作可以保證被刪掉的區間必然不在任何一種最優方案中，因此貪心演算法的選擇一定是最優的。