P1803 凌乱的yyy / 线段覆盖

倚窗倾听风吹雨

https://www.luogu.org/problemnew/show/P1803


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

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

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

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

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

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

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

输入输出样例
输入样例#1：
3
0 2
2 4
1 3
输出样例#1：
2
说明
对于20%的数据，n≤10；
对于50%的数据，n≤1000；
对于70%的数据，n≤100000；
对于100%的数据，n≤1000000，0≤ai＜bi≤1000000。

黄煦喆

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. int n,ans=1,l=1,r=2;
   
5. struct times
   
6. {
   
7.     int a,b;
   
8. }t[1000001];
   
9. bool operator < (times x,times y)
   
10. {
    
11.     return x.b<y.b;
    
12. }
    
13. int main()
    
14. {
    
15.     cin>>n;
    
16.     for(int i=1;i<=n;i++)cin>>t[i].a>>t[i].b;
    
17.     sort(t+1,t+n+1);
    
18.     while(r<=n)
    
19.     {
    
20.         if(t[r].a>=t[l].b)ans++,l=r;
    
21.         r++;
    
22.     }
    
23.     cout<<ans;
    
24.     return 0;
    
25. }
    

复制代码