AT_tupc2024_q Make Intervals Disjoint

给定 $N$ 个半开区间。第 $i$ 个半开区间可以用整数 $L_i, R_i$ 表示为 $[L_i, R_i)$。 你可以对以下操作进行任意次（也可以不进行）： - 从 $2N$ 个整数 $L_1,R_1,L_2,R_2,\dots,L_N,R_N$ 中选择一个，使其值加 $1$ 或减 $1$。 你的目标是让 $N$ 个半开区间 $[L_1,R_1), [L_2,R_2),\dots,[L_N,R_N)$ 互不相交。更严格地说，对于所有满足 $1\le i

输入通过标准输入按以下格式给出。 > $T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$ 每组数据按以下格式输入。 > $N$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_N$ $R_N$

输出共 $T$ 行，第 $i$ 行输出第 $i$ 个测试用例的答案。

### 致 Universal Cup 参赛者 本题将在收录 Universal Cup 时删除。因此，如果在 Universal Cup 中需要用 AtCoder 的成绩，请优先完成本题以外的题目。 ### 样例解释 1 对于第 $1$ 个测试用例，例如： - 将 $R_1$ 减少 $1$； - 将 $L_3$ 增加 $1$； 操作后，三个区间分别变为 $[1,3), [3,7), [7,7)$，它们互不相交。 可以证明无法通过少于 $2$ 次操作达成目标，因此第 $1$ 个测试用例的答案为 $2$。 ### 数据范围 - $1 \le T \le 10^5$ - $2 \leq N \leq 2 \times 10^5$ - $1 \le L_i< R_i \le 10^9$ - 所有测试用例中 $N$ 的总和不超过 $2\times 10^5$ - 输入均为整数。 由 ChatGPT 5 翻译