洛谷 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 3

out:
2
*/

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