CF1285E Delete a Segment

在 $Ox$ 轴上有 $n$ 个线段，分别为 $[l_1, r_1]$、$[l_2, r_2]$、...、$[l_n, r_n]$。线段 $[l, r]$ 覆盖所有从 $l$ 到 $r$（包含端点）的点，即所有满足 $l \le x \le r$ 的 $x$。 这些线段可以任意放置——可以相互包含、重合等。线段也可以退化为一个点，即 $l_i = r_i$ 是允许的。 这些线段的并集是指覆盖与原集合完全相同点集的线段集合。例如： - 如果 $n=3$，线段为 $[3, 6]$、$[100, 100]$、$[5, 8]$，那么它们的并集为 $2$ 个线段：$[3, 8]$ 和 $[100, 100]$； - 如果 $n=5$，线段为 $[1, 2]$、$[2, 3]$、$[4, 5]$、$[4, 6]$、$[6, 6]$，那么它们的并集为 $2$ 个线段：$[1, 3]$ 和 $[4, 6]$。 显然，并集是若干两两不相交的线段的集合。 你的任务是：从给定的 $n$ 个线段中恰好删除一个线段，使得剩下的 $n-1$ 个线段的并集中的线段数尽可能多。 例如，若 $n=4$，线段为 $[1, 4]$、$[2, 3]$、$[3, 6]$、$[5, 7]$，则： - 删除第一个线段后，剩下 $[2, 3]$、$[3, 6]$、$[5, 7]$，它们的并集为 $1$ 个线段； - 删除第二个线段后，剩下 $[1, 4]$、$[3, 6]$、$[5, 7]$，它们的并集为 $1$ 个线段； - 删除第三个线段后，剩下 $[1, 4]$、$[2, 3]$、$[5, 7]$，它们的并集为 $2$ 个线段； - 删除第四个线段后，剩下 $[1, 4]$、$[2, 3]$、$[3, 6]$，它们的并集为 $1$ 个线段。 因此，应该删除第三个线段，答案为 $2$。 请编写程序，求出对于每组数据，删除任意一个线段后，剩下 $n-1$ 个线段的并集中的线段数的最大值。 注意，如果原集合中有多个完全相同的线段，删除时只能删去其中一个。删除后集合中恰好剩下 $n-1$ 个线段。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是 $t$ 组测试数据。 每组测试数据的第一行包含一个整数 $n$（$2 \le n \le 2\cdot10^5$），表示该组线段的数量。接下来的 $n$ 行，每行包含两个整数 $l_i$、$r_i$（$-10^9 \le l_i \le r_i \le 10^9$），表示第 $i$ 条线段的左右端点。 线段的顺序是任意的。 保证所有测试用例中 $n$ 的总和不超过 $2\cdot10^5$。

输出 $t$ 个整数，按输入顺序分别表示每组测试数据的答案。每个答案为删除任意一个线段后，剩余 $n-1$ 个线段的并集中的线段数的最大值。

由 ChatGPT 4.1 翻译