#CF1907D. 线段间跳跃

线段间跳跃

CF1907D Jumping Through Segments

题目描述

\hspace{15pt}Polycarp 正在为一个游戏设计关卡。这个关卡由数轴上的 nn 个区间组成,第 ii 个区间的起点为 lil_i,终点为 rir_i。

\hspace{15pt}玩家从坐标 00 处开始。在一次移动中,玩家可以移动到距离当前位置不超过 kk 的任意点(坐标不必是整数)。在第 ii 次移动后,玩家必须停在第 ii 个区间内,即坐标 xx 满足 li≦x≦ril_i \leqq x \leqq r_i。具体来说:

∙ \hspace{23pt}\bullet\,第一次移动后,玩家必须位于第一个区间(l1l_1 到 r1r_1)内;

∙ \hspace{23pt}\bullet\,第二次移动后,玩家必须位于第二个区间(l2l_2 到 r2r_2)内;

∙ ⋯\hspace{23pt}\bullet\,\cdots

∙ \hspace{23pt}\bullet\,第 nn 次移动后,玩家必须位于第 nn 个区间(lnl_n 到 rnr_n)内。

\hspace{15pt}如果玩家按照上述规则到达第 nn 个区间,则视为完成关卡。Polycarp 发现,对于某些 kk 的取值,关卡无法完成。

\hspace{15pt}Polycarp 不希望关卡太简单,因此他希望你求出能够完成关卡的最小整数 kk。

输入格式

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 t(1≦t≦104)t \left(1 \leqq t \leqq 10^4\right) 代表数据组数,每组测试数据描述如下:

\hspace{15pt}第一行输入一个整数 n(1≦n≦2×105)n \left(1 \leqq n \leqq 2 \times 10^5\right) 代表关卡中的区间数量。

\hspace{15pt}此后 nn 行,第 ii 行输入两个整数 $l_i, r_i \left(0 \leqq l_i \leqq r_i \leqq 10^9\right)$ 代表第 ii 个区间的左右端点。区间之间可能存在重叠。

\hspace{15pt}除此之外,保证单个测试文件中所有测试数据的 nn 之和不超过 2×1052 \times 10^5。

输出格式

\hspace{15pt}对于每一组测试数据,新起一行,输出一个整数,代表能够完成关卡的最小整数 kk。

测试样例

4
5
1 5
3 4
5 6
8 10
0 1
3
0 2
0 1
0 3
3
3 8
10 18
6 11
4
10 20
0 5
15 17
2 2
7
0
5
13

样例 3 解释

\hspace{15pt}在第三组测试数据中,玩家可以按如下方式移动:

∙ \hspace{23pt}\bullet\,从 00 移动到 55(3≦5≦83 \leqq 5 \leqq 8);

∙ \hspace{23pt}\bullet\,从 55 移动到 1010(10≦10≦1810 \leqq 10 \leqq 18);

∙ \hspace{23pt}\bullet\,从 1010 移动到 77(6≦7≦116 \leqq 7 \leqq 11)。

\hspace{15pt}注意,最后一步玩家也可以选择不移动,依然可以完成关卡。