Problem1007--「一本通 1.1 练习 3」线段

1007: 「一本通 1.1 练习 3」线段

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 5  Solved: 3
Submit Status Web Board

Creator:

Description

数轴上有 nnn 条线段,选取其中 kkk 条线段使得这 kkk 条线段两两没有重合部分,问 kkk 最大为多少。

Input

第一行为一个正整数 nnn
在接下来的 nnn 行中,每行有 222 个数 ai,bia_i, b_iai,bi,描述每条线段。

Output

输出一个整数,为 kkk 的最大值。

Sample Input

3
0 2
2 4 
1 3

Sample Output

2

HINT

对于 20%20\%20% 的数据,n≤10n \leq 10n10
对于 50%50\%50% 的数据,n≤103n \leq 10^3n103
对于 70%70\%70% 的数据,n≤105n \leq 10^5n105
对于 100%100\%100% 的数据,n≤106,n \leq 10^6,n106, 0≤ai0ai<bi106

Source/Category


Submit Status