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<j\le N$ 的整数对 $(i,j)$，不存在满足 $L_i\le x<R_i$ 且 $L_j\le x<R_j$ 的实数 $x$。

其中，当 $L\ge R$ 时，半开区间 $[L,R)$ 表示为空集，空集与任何区间都不相交。

请计算为实现目标所需的最小操作次数。

对于给定的 $T$ 个测试用例，请分别输出每个测试用例的答案。

输入通过标准输入按以下格式给出。

$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 翻译