Problem6023--膜拜

6023: 膜拜

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

小鱼有 $n$ 名优秀的粉丝。
粉丝们得知小鱼将会在一条直线上出现,打算去膜他。为了方便,粉丝们在这条直线上建立数轴。
第 $i$ 名粉丝有一个侦查区间 $[l_i,\ r_i]$。如果小鱼在 $j\ (l_i≤j≤r_i)$ 处出现,这名粉丝将立刻发现并膜他。
小鱼希望膜他的人越多越好,但是他不能分身,因此只能选择一个位置出现。
小鱼想知道自己最多能被多少个人膜。

Input

第一行一个整数 $n$ —— 粉丝的个数。
接下来 $n$ 行,每行两个整数 $l_i,\ r_i$,分别表示第 $i$ 名粉丝的侦查区间的两个端点。两个数之间用空格隔开。

Output

共一行,一个整数,表示小鱼最多能被多少人膜。

Constraints

对于 $20\%$ 的数据,$n≤2$
对于 $60\%$ 的数据,$n≤2,000$
对于 $100\%$ 的数据,$1 ≤ n ≤ 5 × 10^4,\ 1 ≤ l_i ≤ r_i <2^{30}$

Sample 1 Input

4
3 5
4 8
1 2
5 10

Sample 1 Output

3

如图所示,小鱼可出现在 $5$ 处,此时第 $1,\ 2,\ 4$ 号粉丝可以膜他。小鱼最多只能被 $3$ 个粉丝膜拜。

Source/Category