Problem1411--线段

1411: 线段

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 45  Solved: 19
[Submit] [Status] [Web Board] [Creator:]

Description

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

Input

第一行为一个正整数 n;

在接下来的 n 行中,每行有 2 个数 ai,bi,描述每条线段。

Output

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

Sample Input Copy

3
0 2
2 4 
1 3

Sample Output Copy

2

HINT

对于 20% 的数据,n≤10;

对于 50% 的数据,n≤10^3

对于 70% 的数据,n≤10^5

对于 100% 的数据,n≤10^6,0≤ai≤bi≤10^6

Source/Category

贪心