问题 h: 线段

问题 h: 线段

时间限制: 1 Sec  内存限制: 128 MB
提交: 26  解决: 13
[提交][状态][讨论版][命题人:]

题目描述

在一个数轴上有n条线段,现要选取其中k条线段使得这k条线段两两没有重合部分(端点可以重合),问最大的k为多少。

输入

输入文件的第1行为一个正整数n,下面n行每行2个数字ai,bi,描述每条线段。

输出

输出文件仅包括1个整数,为k的最大值

样例输入

3

0 2

2 4

1 3

样例输出

2

提示


对于20%的数据,n10



对于50%的数据,n1000



对于70%的数据,n100000



对于100%的数据,n10000000ai<bi≤1000000

[提交][状态]