洛谷 P1803：凌乱的yyy / 线段覆盖 ← 贪心算法

【题目来源】
https://www.luogu.com.cn/problem/P1803

【题目背景】
快 noip 了，yyy 很紧张！

【题目来源】
现在各大 oj 上有 n 个比赛，每个比赛的开始、结束的时间点是知道的。
yyy 认为，参加越多的比赛，noip 就能考的越好（假的）。
所以，他想知道他最多能参加几个比赛。
由于 yyy 是蒟蒻，如果要参加一个比赛必须善始善终，而且不能同时参加 2 个及以上的比赛。

【输入格式】
第一行是一个整数 n，接下来 n 行每行是 2 个整数 ai,bi（ai<bi），表示比赛开始、结束的时间。

【输出格式】
一个整数最多参加的比赛数目。

【输入样例】
3
0 2
2 4
1 3

【输出样例】
2

【说明/提示】
对于 20% 的数据，n≤10；
对于 50% 的数据，n≤10^3；
对于 70% 的数据，n≤10^5；
对于 100% 的数据，1≤n≤10^6，0≤ai<bi≤10^6。

【算法分析】
首先，对结束时间 to 从小到大进行排序；
其次，令比较基准 t = -1，并从第 i=0 个元素开始依次比较。如果第 i 个元素的开始时间 from 在比较基准 t 之后（即 a[i].from>=t），那么 ans++，把第 i 个元素的结束时间 to 作为新的比较基准 t（即 t=a[i].to），如此循环即可。

【算法代码】

#include <bits/stdc++.h>
using namespace std;const int maxn=1e6+5;struct Node {int from;int to;
} a[maxn];int up(Node u,Node v) {return u.to<v.to;
}int main() {int n;cin>>n;for(int i=0; i<n; i++) {cin>>a[i].from>>a[i].to;}sort(a,a+n,up);int ans=0;int t=-1;for(int i=0; i<n; i++) {if(a[i].from>=t) {ans++;t=a[i].to;}}cout<<ans<<endl;return 0;
}/*
in:
3
0 2
2 4
1 3out:
2
*/

【参考文献】
https://www.luogu.com.cn/problem/solution/P1803
https://www.acwing.com/file_system/file/content/whole/index/content/8430847/