← 返回题目列表

AtCoder · past202212_l

L. 段

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

问题陈述

你被给予 N 片段 [L_1, R_1], [L_2, R_2], \ldots, [L_N, R_N] 。

一个子集 S 集合中的 \lbrace 1, 2, \ldots, N \rbrace 据说是 好套装 如果:

  • 对于所有人 i, j \in S至少满足以下两个条件中的一个:
    • 线段 [L_i, R_i] 包含线段 [L_j, R_j];
    • 线段 [L_j, R_j] 包含线段 [L_i, R_i].

这里,线段 [L, R] 被认为包含另一个线段 [L', R'] 当且仅当 L \leq L' 和 R' \leq R.

找到一个好集合的最大可能大小。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq L_i < R_i \leq 10^9
  • 输入中的所有值都是整数。

输入

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

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N

输出

打印答案。


示例输入 1

4
1 3
2 4
3 4
1 4

示例输出 1

3

该套 \lbrace 2, 3, 4 \rbrace 是具有最大大小的好集合。实际上,

  • 为 2, 3 \in S, [L_2, R_2] 包含 [L_3, R_3];
  • 为 2, 4 \in S, [L_4, R_4] 包含 [L_2, R_2];和
  • 为 3, 4 \in S, [L_4, R_4] 包含 [L_3, R_3];

因此大小 3 。


示例输入 2

3
0 1
0 1
0 1

示例输出 2

3

示例输入 3

9
1 6
1 3
3 6
4 6
2 5
1 2
3 4
3 5
2 7

示例输出 3

4