CF1907D Jumping Through Segments

Polycarp 正在为一个游戏设计关卡。这个关卡由数轴上的 $n$ 个区间组成，第 $i$ 个区间的起点为 $l_i$，终点为 $r_i$。 玩家从坐标 $0$ 处开始。在一次移动中，玩家可以移动到距离当前位置不超过 $k$ 的任意点。在第 $i$ 次移动后，玩家必须停在第 $i$ 个区间内，即坐标 $x$ 满足 $l_i \le x \le r_i$。具体来说： - 第一次移动后，玩家必须在第一个区间（$l_1$ 到 $r_1$）内； - 第二次移动后，玩家必须在第二个区间（$l_2$ 到 $r_2$）内； - ... - 第 $n$ 次移动后，玩家必须在第 $n$ 个区间（$l_n$ 到 $r_n$）内。 如果玩家按照上述规则到达第 $n$ 个区间，则视为完成关卡。Polycarp 发现，对于某些 $k$ 的取值，关卡无法完成。 Polycarp 不希望关卡太简单，因此他希望你求出能够完成关卡的最小整数 $k$。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示关卡中的区间数量。 接下来的 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$0 \le l_i \le r_i \le 10^9$），表示第 $i$ 个区间的左右端点。区间可能有重叠。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示能够完成关卡的最小 $k$。

在第三个样例中，玩家可以按如下方式移动： - 从 $0$ 移动到 $5$（$3 \le 5 \le 8$）； - 从 $5$ 移动到 $10$（$10 \le 10 \le 18$）； - 从 $10$ 移动到 $7$（$6 \le 7 \le 11$）。 注意，最后一步玩家也可以选择不移动，依然可以完成关卡。 由 ChatGPT 4.1 翻译