C++贪心实现区间覆盖问题

区间覆盖问题是指给定若干个区间，从中选出尽可能少的区间，使得所有的区间都被覆盖。贪心算法可以解决这个问题，具体步骤如下：

1. 将所有区间按右端点从小到大排序。

2. 选取右端点最小的区间，将其加入覆盖区间集合中。

3. 从剩余的区间中，选择左端点在已覆盖区间集合中右端点之后的区间中右端点最小的区间，将其加入覆盖区间集合中。

4. 重复步骤3，直到所有的区间都被覆盖。

下面是C++代码实现：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct Interval {
    int l, r;
    bool operator<(const Interval& other) const {
        return r < other.r;
    }
};

vector<Interval> intervalCover(vector<Interval>& intervals) {
    vector<Interval> res;
    sort(intervals.begin(), intervals.end());
    int n = intervals.size(), i = 0;
    while (i < n) {
        int r = intervals[i].r;
        res.push_back(intervals[i++]);
        while (i < n && intervals[i].l <= r) {
            ++i;
        }
    }
    return res;
}

int main() {
    vector<Interval> intervals{{1, 3}, {2, 4}, {3, 6}, {4, 7}, {5, 8}, {6, 9}};
    vector<Interval> res = intervalCover(intervals);
    for (auto& interval : res) {
        cout << "[" << interval.l << ", " << interval.r << "] ";
    }
    cout << endl; // output: [1, 3] [4, 7] [6, 9] 
    return 0;
}