题目背景

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

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define MAXN 2000005
using namespace std;
struct cc{
int bg,ed;
}nod[MAXN];
bool cmp(cc a,cc b){
if(a.ed==b.ed) return a.bg<b.bg;
else return a.ed<b.ed;
} int N,p=1,lst_time,ans; int main(){
// freopen("01.in","r",stdin); scanf("%d",&N);
for(int i=1;i<=N;i++){scanf("%d%d",&nod[i].bg,&nod[i].ed);} sort(nod+1,nod+N+1,cmp); for(int i=0;i<=1000005&&p<=N;i++){
while( p<=N && ( nod[p].ed<i || lst_time>nod[p].bg ) ) ++p;
// cout<<nod[p].bg<<" "<<nod[p].ed<<endl; if(nod[p].ed==i&&p<=N&&lst_time<=nod[p].bg){
lst_time=i;
++ans;
++p;
}
}
cout<<ans<<endl;
return 0;
}

  

选取最早结束的即可

Line 26 p<=N没写RE了sad>_<

最新文章

  1. Runtime解决屏幕旋转问题
  2. QuanbenSoft Windows Runtime (Windows Store)Apps 应用及其框架总览
  3. oracle 11g 新特性UTL_TCP、UTL_HTTP 和 UTL_SMTP程序包发邮件
  4. JavaScript验证函数大全
  5. Tomcat找不到service.bat文件
  6. linux vim用法总结
  7. UVALive 7274 Canvas Painting (优先队列)
  8. OpenRisc-42-or1200的ALU模块分析
  9. c++冒泡排序的模板函数设计
  10. Javascript 进阶 封装
  11. Referer反反盗链
  12. linux下 ls -l 命令显示结果每一列代表什么意思
  13. 推荐一款好用的office转换PDF工具
  14. telnet客户端操作memcached增删改查
  15. 2019-1-18 Spark 机器学习
  16. 配置apache使用https访问
  17. 并发基础(九) java线程的终止与中断
  18. STS或eclipse安装SVN插件
  19. npm、webpack、Gulp 中文教程
  20. synchronized锁优化

热门文章

  1. iptables下state的4种形式
  2. ASP.NET的Cookie和Session
  3. SQLServer索引
  4. 针对较大基数的排列组合算法Java实现类(n选m)
  5. wp8 入门到精通 仿QQPivot 提示数量
  6. PHP二维数组的分页
  7. 【rqnoj378】 约会计划
  8. javascript 的基础笔记
  9. 稀疏矩阵存储格式总结+存储效率对比:COO,CSR,DIA,ELL,HYB
  10. Build an ETL Pipeline With Kafka Connect via JDBC Connectors