← 返回题目列表

AtCoder · past20_h

H. 温度管理

中文机器翻译题面 查看原题

问题陈述

N 人们来泡温泉。 i如果能泡一个温度介于 L_i 和 R_i 度,包括在内。

您可以在任何温度下准备任意数量的温泉。然而,每个温泉只能有一个设定温度。

至少需要准备多少个温泉才能让所有 N 人们满意吗?

约束

  • 1 \leq N \leq 2 \times 10^{5}
  • 1 \leq L_i \leq R_i \leq 10^{9}
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N

输出

打印您需要准备的最少温泉数量。


示例输入 1

5
37 40
43 45
40 42
35 39
39 43

示例输出 1

3

如果您准备三个温泉 39, 41,和 45 度,大家都会满意的。然而,准备两个或更少的温泉永远无法让所有人都满意。因此, 3 。


示例输入 2

7
27 50
40 43
55 60
25 30
33 49
35 39
32 45

示例输出 2

4