【CSP】CSP-XL 2025辽宁复赛真题-第三题, 小L打比赛（match）

1#include <algorithm>
2#include <iostream>
3
4struct Match {
5    int start = 0; // 比赛开始时间
6    int end = 0;   // 比赛结束时间
7};
8
9// 按结束时间升序排序的比较函数
10bool cmp(Match a, Match b) { return a.end < b.end; }
11
12// 全局数组，存储所有比赛
13struct Match matches[500005];
14
15int main() {
16    freopen("match.in", "r", stdin);
17    freopen("match.out", "w", stdout);
18    int n;
19    std::cin >> n;
20    // 读入 n 场比赛的起止时间
21    for (int i = 0; i < n; i++) {
22        std::cin >> matches[i].start >> matches[i].end;
23    }
24    // 按结束时间升序排序，为贪心选择做准备
25    std::sort(matches, matches + n, cmp);
26    int count = 1;              // 至少能打一场比赛
27    int cur_end = matches[0].end; // 当前所选最后一场的结束时间
28
29    // 贪心选择：每次挑结束时间最早且不与上一场比赛冲突的比赛
30    for (int i = 1; i < n; i++) {
31        if (matches[i].start > cur_end) { // 无冲突
32            count++;
33            cur_end = matches[i].end;     // 更新最后结束时间
34        }
35    }
36    std::cout << count << std::endl; // 输出最多能观看的比赛场数
37    return 0;
38}