一、题意

输入M以及若干区间[xi, yi)，要求你从中取出最少的区间，使得这些区间能覆盖[0, M)。
输出最少的数量，以及选出的区间。

二、解析

经典的区间覆盖问题。
用贪心的思想。将所有区间按照左端点从小到大排列。
用cur表示当前的“截取点”,在截取点之前的长度是毫无意义的。比如，在初始状态时由于我们要覆盖[0，M)，所以cur=0，此时对于一个区间比如[-2, 3)，它小于0的那一段是没有用的。
因此我们首先从区间中遍历到的是会被截取点截断的若干区间，在这些区间中，我们贪心地选择剩余长度最长的（尽可能覆盖更多的长度），将它地右端点作为max_b，此时我们需要覆盖的区间就变成了[max_b，M)。于是类似的，在下一轮时我们将截取点cur:=max_b，然后以此类推。
当max_b>=M时，说明已经完全覆盖完毕了。

三、代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct Internal {
    int l, r;
    Internal() {}
    Internal(int l, int r) : l(l), r(r) {}
    bool operator < (const Internal & rhs) const {
        return l < rhs.l;
    }
};
int kase, M;

int main() {
    cin >> kase;
    while(kase --) {
        cin >> M;
        vector<Internal> vec;
        int x, y;
        while(cin >> x >> y && (x || y)) vec.push_back(Internal(x, y));

        sort(vec.begin(), vec.end());
        int s = 0, t = M;
        auto L = vec.begin();
        vector<Internal> ans;
        while(s < t && L != vec.end()) {  // 右端点无法覆盖
            auto R = upper_bound(L, vec.end(), Internal(s, s));
            if(L == R) break;  // 左端点无法覆盖
            auto chosen = *max_element(L, R, [](const Internal& a, const Internal& b) {
                return a.r < b.r;
            });
            ans.push_back(chosen);
            L = R, s = chosen.r;
        }

        if(s < t) cout << 0 << endl;  // 无法覆盖完全
        else {
            cout << ans.size() << endl;
            for(const auto& p : ans) cout << p.l << " " << p.r << endl;
        }
        if(kase) cout << "\n";
    }
}

四、归纳

  • 区间覆盖问题：按左端点排序，维护“截取点”，总是选择被截取后剩余长度最长的区间。