1429：线段

时间限制: 1000 ms
内存限制: 65536 KB
提交数: 5437
通过数: 2540

题目描述

在一个数轴上有 $n$ 条线段，现选取其中 $k$ 条线段使得这 $k$ 条线段两两没有重合部分，问最大的 $k$ 为多少？

第一行为一个正整数 $n$ ，表示线段的条数；

接下来 $n$ 行，每行两个整数 $a_i$ , $b_i$ ，描述每条线段的起点和终点。

输出一个整数，表示 $k$ 的最大值。

对于 $20\%$ 的数据， $n \le 10$ 。

对于 $50\%$ 的数据， $n \le 1000$ 。

对于 $70\%$ 的数据， $n \le 100000$ 。

对于 $20\%$ 的数据， $n \le 1000000$ , $0 \le a_i < b_i \le 1000000$ 。