AT_abc214_e [ABC214E] Packing Under Range Regulations

题目描述

请针对 $T$ 个测试用例，解决以下问题。

有 $10^9$ 个编号为 $1,2,\dots,10^9$ 的箱子，以及 $N$ 个编号为 $1,2,\dots,N$ 的球。
每个箱子最多只能放 $1$ 个球。
请判断是否可以将所有 $N$ 个球都放入箱子中，且满足以下条件：

• 对于每个 $1 \leq i \leq N$，编号为 $i$ 的球必须放入编号在 $L_i$ 到 $R_i$ 之间的某个箱子中。

输入格式

输入从标准输入读入。第 $1$ 行为：

$T$

接下来有 $T$ 个测试用例。每个测试用例的格式如下：

$N$ $L_1$ $R_1$ $L_2$ $R_2$ $\dots$ $L_N$ $R_N$

输出格式

输出共 $T$ 行。
对于第 $i$ 个测试用例，如果可以将所有 $N$ 个球都按要求放入箱子中，输出 Yes，否则输出 No。
判题时不区分英文字母大小写。

输入输出样例 #1

输入 #1

2
3
1 2
2 3
3 3
5
1 2
2 3
3 3
1 3
999999999 1000000000

输出 #1

Yes
No

说明/提示

数据范围

• $1 \leq T \leq 2 \times 10^5$
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq L_i \leq R_i \leq 10^9$
• 所有测试用例中 $N$ 的总和不超过 $2 \times 10^5$

样例解释 1

该输入包含 $2$ 个测试用例。

• 对于第 $1$ 个测试用例，可以如下分配球与箱子，使得所有 $3$ 个球都能被放入箱子中，输出 Yes。
  • 将球 $1$ 放入箱子 $1$。
  • 将球 $2$ 放入箱子 $2$。
  • 将球 $3$ 放入箱子 $3$。
• 对于第 $2$ 个测试用例，无法满足条件将所有 $5$ 个球都放入箱子中，因此输出 No。

由 ChatGPT 4.1 翻译