区间覆盖问题

一、问题描述

区间覆盖问题是指，给定一些区间，选出最少的区间，使其可以完全覆盖另一个给定的区间。例如，在给定区间[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.start;
    }
    return a.end > 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中还剩下的所有区间仍然构成区间覆盖问题，且仍然可以先按左端点从小到大排序，然后将左端点小于等于最优区间的区间删除。每一步操作可以保证被删掉的区间必然不在任何一种最优方案中，因此贪心算法的选择一定是最优的。

四、时间复杂度分析

该算法的时间复杂度为O(nlogn)，主要是因为需要对区间按照左端点排序。

五、总结

区间覆盖问题是一个经典的NP难问题，需要通过高效的算法来解决。本文介绍了一种朴素的贪心算法，该算法每次选择可以覆盖最多区间的区间，并最终保证选择的区间数最小。同时，也给出了证明该算法正确性的详细过程，并对时间复杂度进行了分析。