Score : $500$ points

问题描述

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

有 $10^9$ 个编号为 $1,2,\dots,10^9$ 的盒子和 $N$ 个编号为 $1,2,\dots,N$ 的球。
每个盒子最多只能容纳一个球。
确定是否有可能将所有 $N$ 个球放入盒子中，使得满足以下条件：

• 对于从 $1$ 到 $N$ 的每个整数 $i$，编号为 $i$ 的球位于编号在 $L_i$ 和 $R_i$（包含）之间的盒子里。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Solve the following problem for $T$ test cases.

There are $10^9$ boxes numbered $1,2,\dots,10^9$ and $N$ balls numbered $1,2,\dots,N$.
Each box can contain at most one ball.
Determine whether it is possible to put all $N$ balls in the boxes so that the following condition will be satisfied.

• For each integer $i$ from $1$ through $N$, the ball numbered $i$ is in a box numbered between $L_i$ and $R_i$ (inclusive).

Constraints

• $1 \le T \le 2 \times 10^5$
• $1 \le N \le 2 \times 10^5$
• $1 \le L_i \le R_i \le 10^9$
• The sum of $N$ across the test cases in one input is at most $2 \times 10^5$.

Input

Input is given from Standard Input. The first line is in the following format:

$T$

Then, $T$ test cases follows, each of which is in the following format:

$N$

$L_1$ $R_1$

$L_2$ $R_2$

$\dots$

$L_N$ $R_N$

Output

Your output should have $T$ lines.
In the $i$-th $(1 \le i \le T)$ line, print Yes if it is possible to put all $N$ balls in the boxes so that the condition will be satisfied in the $i$-th test case in the input, and printNo otherwise.
The checker is case-insensitive; it will accept both uppercase and lowercase letters.

Sample Input 1

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

Sample Output 1

Yes
No

This input contains two test cases.

• In the $1$-st test case, the following way to put the three balls would satisfy the condition, so we should print Yes.

  • Put Ball $1$ in Box $1$.
  • Put Ball $2$ in Box $2$.
  • Put Ball $3$ in Box $3$.

• In the $2$-nd test case, there is no way to put the five balls to satisfy the condition, so we should print No.

update @ 2024/3/10 09:31:44