UOJ Logo

NOI.AC

1S 512MB
Statistics

选择区间

输入m个区间,你希望从中选择尽量多的区间,使得两两不相交,也不能有公共端点。

输入描述

第一行一个整数m,接下来m行,每行两个整数$x_i, y_i$,表示$x_i$到$y_i$的区间。

输出描述

输出一行一个整数,表示最多选择多少个区间。

样例输入

4
1 1
2 2
3 3
2 3

样例输出

3

数据规模与约定

对于100%的数据,满足$1 <= m <= 1e5, 1 <= x_i <= y_i <= 1e9$

对于30%的数据,满足$1 <= m <= 20$

对于70%的数据,满足$1 <= m <= 1000$