问题 3210 --熊猫胖达

3210: 熊猫胖达

时间限制: 1 Sec  内存限制: 256 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

胖达是大熊猫的昵称。

一只成年大熊猫需要有自己独立的生活区域,如果两只成年大熊猫在同一时间进入同一片区域,很可能会发生打斗事件。

大熊猫保护中心计划将保护区划分成若干座山头,让胖达们都过上没有冲突的安逸生活。当然如果为每位胖达分配一个山头是最理想的,但中心计划安置数十万只胖达 —— 这是个长远计划(截至2024年,世界上共有近 1900 只大熊猫),而保护区面积有限,这样做会使得每个山头面积过于局促。于是中心负责人找到了你,带着所有胖达的活跃时间表,请你帮助他们计算一下,如果让所有活跃时间段内的胖达都位于不同的山头,最少需要建设多少个山头?

注意:要求是任何一个山头任何时间点都不能存在超过一只处于活跃时间段的大熊猫。

输入

输入在第一行给出正整数 n(≤10^5),为胖达数量。 

随后 n 行,每行两个正整数l和r,表示每一位胖达的活跃时间段为【l,r】(闭区间)。

输出

在一行中输出保护中心最少需要建设的山头的数量。

样例输入

4
3 4
4 6
1 2
5 7

样例输出

2

提示

1 ≤ n≤ 10^5,1 ≤ l, r ≤ 1000。

来源

[提交][状态]