241702 - 线段(line )

题目描述

题目描述

数轴上有 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^6, 0 \leq a_i < b_i \leq 10^6

题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 7
通过人数 6
金币数量 1 枚
难度 入门


上一题 下一题