普及-每日一题洛谷P1683
题目描述
现在各大 oj 上有 \(n\) 个比赛，每个比赛的开始、结束的时间点是知道的。
yyy 认为，参加越多的比赛，noip 就能考的越好（假的）。
所以，他想知道他最多能参加几个比赛。
由于 yyy 是蒟蒻，如果要参加一个比赛必须善始善终，而且不能同时参加 \(2\) 个及以上的比赛。
输入格式
第一行是一个整数 \(n\)，接下来 \(n\) 行每行是 \(2\) 个整数 \(a_{i},b_{i}\ (a_{i}<b_{i})\)，表示比赛开始、结束的时间。
输出格式
一个整数最多参加的比赛数目。
样例输入
3
0 2
2 4
1 3
样例输出
2
提示
- 对于 \(20\%\) 的数据，\(n \le 10\)；
- 对于 \(50\%\) 的数据，\(n \le 10^3\)；
- 对于 \(70\%\) 的数据，\(n \le 10^{5}\)；
- 对于 \(100\%\) 的数据，\(1\le n \le 10^{6}\)，\(0 \le a_{i} < b_{i} \le 10^6\)。
题目可以转化为求在一条数轴上，不相互覆盖的线段的最大数量
输入线段的长度，可以基于贪心的想法，把每个右端点的线段优先考虑，这是因为每次选取结束时间最靠前的比赛是当前的最优解
线段覆盖问题取每一次的最优解可以得到全局的最优解
首先将线段的参数读入：
struct game
{
int st, ed;
};
game a[100010];//定义结构体
for (int i = 0; i < n; i++) cin >> a[i].st >> a[i].ed;//存入左右端点
然后可以按照ed从小到大排序，这里使用sort函数，配置cmp实现
bool cmp(game x, game y) {
return x.ed < y.ed;
}
sort(a, a + n, cmp);
然后遍历全部的线段，每次取最优解（从\(0\)开始）
int r = 0;//定义当前位置
for (int i = 0; i < n; i++) {
if (r <= a[i].st) {//当前位置小于当前线段的左端点，可以放入
ans++;//答案++
r = a[i].ed;//更新当前位置
}
}
完整AC代码：
#include <iostream>
#include <algorithm>
#include <cstring>
#define streampreset() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);//自定义关闭同步流
using namespace std;
struct game
{
int st, ed;
};
game a[100010];
bool cmp(game x, game y) {
return x.ed < y.ed;
}
int main()
{
streampreset();//读入数据较大，关闭同步流加速读入
int n， ans = 0;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i].st >> a[i].ed;
sort(a, a + n, cmp);
int r = 0;
for (int i = 0; i < n; i++) {
if (r <= a[i].st) {
ans++;
r = a[i].ed;
}
}
cout << ans;
return 0;
}