题意分析

给定一个M值，给定一系列线段，要求从这些线段中找出最少能付给[0,M]的线段

解题思路

题中说有大量的线段数据，首先排除一下不可能出现的线段，不难看出，如果线段的最右端小于0或者最右端大于M，那么这个线段一定不可能覆盖[0，M]。除此之外的线段才是有效线段。题目要求将线段以左端升序输出，我们不妨以左端升序排列，左端一样的用右端降序排列，这是因为我们希望用最少的线段覆盖，那么长的线段优先级高。使用priority_queue优先队列存储数据，方便我们找到右端最大的线段。初始定义current_end 为 0，不断用最大的右端覆盖current_end，直到大于或等于M为止。

标程

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

struct Segment {
    int L, R;
    Segment(int l, int r) : L(l), R(r) {}
};

bool compareSegment(const Segment& a, const Segment& b) {
    return (a.L != b.L) ? (a.L < b.L) : (a.R > b.R);
}

struct CompareR {
    bool operator()(const Segment& a, const Segment& b) {
        return a.R < b.R;
    }
};

int main() {
    int M;
    scanf("%d", &M);

    vector<Segment> segments;
    int L, R;
    while (scanf("%d %d", &L, &R) == 2) {
        if (L == 0 && R == 0) break;
        int effectiveL = max(L, 0);
        int effectiveR = min(R, M);
        if (effectiveL < effectiveR) {
            segments.emplace_back(L, R);
        }
    }

    if (segments.empty()) {
        printf("No solution\n");
        return 0;
    }

    sort(segments.begin(), segments.end(), compareSegment);

    int current_end = 0;
    int i = 0;
    priority_queue<Segment, vector<Segment>, CompareR> pq;
    vector<Segment> result;

    while (current_end < M) {
        while (i < segments.size() && segments[i].L <= current_end) {
            pq.push(segments[i]);
            i++;
        }

        if (pq.empty()) {
            printf("No solution\n");
            return 0;
        }

        Segment top = pq.top();
        pq.pop();

        if (top.R <= current_end) {
            printf("No solution\n");
            return 0;
        }

        result.push_back(top);
        current_end = top.R;
    }

    printf("%d\n", (int)result.size());
    for (const auto& seg : result) {
        printf("%d %d\n", seg.L, seg.R);
    }

    return 0;
}