moxin的学霸养成日记

TimeLimit:1000MS  MemoryLimit:32MB
64-bit integer IO format:%lld
未提交 | 登录后收藏
Problem Description

由于moxin非常热爱学习,总是在寻找能够偷偷学习的途径,现在他在校外成功找到了一个补习机构,补习机构补的每节课都是不同的,所以moxin每节课都想上。可是补习机构每节课安排的时间可能会有冲突,以至于moxin在上任意一节课时,不能再上与当前这节课有时间冲突的课了,所以moxin觉得非常悲伤,没法偷偷学习了。moxin已经知道了排课计划,所以moxin专门来威胁你们,要求你们帮他看看,他在这n节课中,最多能上多少节课。(时间不限,毕竟moxin喜欢学习)

时间冲突的定义是,两节课的时间有交集关系,例如[1,3]与[2,4]冲突了,但是[1,3]与[3,4]并不冲突。(因为moxin不需要休息,总是连着上课,所以上一节课刚结束就可以连着上下一节课)

Input

多组数据输入

第一行包含一个整数n(1≤n≤1000000),说明有多少节课是可以选择的。

第2行至n+1行,每行包含2个整数,ai为当前这节课的开始时间,bi为当节课的结束时间,保证bi>ai。

1<=ai<=1000000,1<=bi<=1000000

Output

输出一个整数表示moxin最多能够学习的课的个数。

SampleInput
3
0 2
2 4
1 3
SampleOutput
2
Submit
题目统计信息详细
总AC数43
通过人数39
尝试人数42
总提交量102
AC率38.24%
AC该题后可以添加标签
贴完标签可以获得20ACB。
并且可以获得本题所有提交代码查看权限。
点击标题可以显示标签。
如果你还没认真思考过这题,请不要查看标签
如果您已经通过了该题,请务为该题贴上标签
作者

T^T Online Judge

[BUG反馈] [FAQ] [闽ICP备17026590号-1]
当前版本:3.24 系统时间: