Logo Quest Online Judge

QOJ

时间限制:1 s 空间限制:512 MB

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

统计

题目描述

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

输入格式

第一行为一个正整数 $ n $;

在接下来的 $ n $ 行中,每行有 $ 2 $ 个数 $ a_{i} $, $ b_{i} $,描述每条线段。

输出格式

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

样例输入

3
0 2
2 4 
1 3

样例输出

2

数据范围与提示

对于 $ 20\% $ 的数据,$ n \leq 10 $;

对于 $ 50\% $ 的数据,$ n \leq 10^{3} $;

对于 $ 70\% $ 的数据,$ n \leq 10^{5} $;

对于 $ 100\% $ 的数据,$ n \leq 10^{5} $,$ 0 \leq a_{i} < b_{i} \leq 10^{6} $ 。