【题目来源】
洛谷：P1803 凌乱的yyy / 线段覆盖 - 洛谷 (luogu.com.cn)
【题目描述】
现在各大 oj 上有 \(n\) 个比赛，每个比赛的开始、结束的时间点是知道的。
yyy 认为，参加越多的比赛，noip 就能考的越好（假的）。
所以，他想知道他最多能参加几个比赛。
由于 yyy 是蒟蒻，如果要参加一个比赛必须善始善终，而且不能同时参加 \(2\) 个及以上的比赛。
【输入】
第一行是一个整数 \(n\)，接下来 \(n\) 行每行是 \(2\) 个整数 \(a_i,b_i(a_i\le b_i)\)，表示比赛开始、结束的时间。
【输出】
一个整数最多参加的比赛数目。
【输入样例】
3
0 2
2 4
1 3
【输出样例】
2
【解题思路】
【算法标签】
《洛谷 P1803 线段覆盖》 #搜索# #贪心# #排序#
【代码详解】
#include <bits/stdc++.h> // 包含所有标准库头文件
using namespace std;// 定义游戏结构体
struct game
{int l; // 游戏开始时间int r; // 游戏结束时间
} gs[1000005]; // 最多1000005个游戏// 自定义排序比较函数：按游戏结束时间升序排序
bool cmp(game g1, game g2)
{return g1.r < g2.r;
}int main()
{int n; // 游戏总数int ans = 0; // 最多能玩的游戏数量int mark = 0; // 记录上一个游戏的结束时间// 输入游戏总数cin >> n;// 输入每个游戏的开始和结束时间for (int i = 0; i < n; i++) cin >> gs[i].l >> gs[i].r;// 按游戏结束时间从早到晚排序sort(gs, gs + n, cmp);// 贪心算法：选择结束时间最早的游戏for (int i = 0; i < n; i++) {// 如果当前游戏开始时间不早于上一个游戏的结束时间if (mark <= gs[i].l) {ans++; // 可以玩这个游戏mark = gs[i].r; // 更新最后玩的游戏结束时间}}// 输出最多能玩的游戏数量cout << ans;return 0;
}
【运行结果】
3
0 2
2 4
1 3
2