问题 O: 线段

问题 O: 线段

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 256 MiB

题目描述

【题目描述】

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

输入格式

第一行为一个正整数 n

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

输出格式

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

输入

3

0 2

2 4

1 3

输出

2

数据范围与提示

对于 20% 的数据,n≤10

对于 50% 的数据,n≤103

对于 70% 的数据,n≤105

对于 100% 的数据,n≤106 0<a<b<106

 

 

输入

第一行为一个正整数 n;

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

输出

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

样例输入 复制

3
0 2
2 4
1 3

样例输出 复制

2