最多能打多少场比赛呢

凌乱的yyy / 线段覆盖

题目背景

快 noip 了，yyy 很紧张！

题目描述

现在各大 oj 上有 $n$ 个比赛，每个比赛的开始、结束的时间点是知道的。

yyy 认为，参加越多的比赛，noip 就能考的越好（假的）。

所以，他想知道他最多能参加几个比赛。

由于 yyy 是蒟蒻，如果要参加一个比赛必须善始善终，而且不能同时参加 $2$ 个及以上的比赛。

输入格式

第一行是一个整数 $n$ ，接下来 $n$ 行每行是 $2$ 个整数 $a_i,b_i$ ( $a_i<b_i$ )，表示比赛开始、结束的时间。

输出格式

一个整数最多参加的比赛数目。

样例 #1

样例输入 #1

3
0 2
2 4
1 3

样例输出 #1

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$。

思路

要求最多能打多少场比赛，那么早结束的比赛就要先打，所以要按比赛结束时间来排序。设定一个变量en来储存上一次比赛结束时间，如果这一次比赛开始时间大于等于上一次比赛结束时间，那么这场比赛就可以打，接着更新en为这次比赛结束时间，方便下一个比较。这里我想分享一下我讨论的一个问题：当区间包含的时候，比如2 3、2 4、3 4，因为原先按比赛结束时间排好了序，所以2 3会打，然后因为2 4的比赛开始时间小于2 3比赛结束时间，所以2 4不会打，接着 3 4会打。也就是说，区间重合时，会筛选出区间内的比赛。因为最外层的那场比赛开始时间小，结束时间大，会被筛掉的。

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+10;
struct Tim
{int s,e;
}t[N];
bool cmp(Tim a,Tim b)
{return a.e<b.e;//按照比赛结束时间从小到大排序
}
int main()
{int n;cin>>n;for(int i=0;i<n;i++){cin>>t[i].s>>t[i].e;}sort(t,t+n,cmp);int en=0;long long cnt=0;for(int i=0;i<n;i++){if(t[i].s>=en)//大于上次比赛结束时间，区间不重合{en=t[i].e;//更新比赛结束时间cnt++;}else{continue;}}cout<<cnt;return 0;
}