← 返回题目列表

Codeforces · 1285/E

E. 删除段

中文机器翻译题面 查看原题

$$$Ox$$$ 轴 $$$[l_1, r_1]$$$、$$$[l_2, r_2]$$$、...、$$$[l_n, r_n]$$$ 上有 $$$n$$$ 段。线段 $$$[l, r]$$$ 涵盖了从 $$$l$$$ 到 $$$r$$$ 的所有点,因此所有 $$$x$$$ 都满足 $$$l \le x \le r$$$。

段可以任意放置 - 彼此内部、重合等等。线段可以退化为点,即 $$$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$$$ 段,该程序将找到 $$$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$$$),其中 $$$l_i$$$ 和 $$$r_i$$$ 是第 $$$i$$$ 段的左边界和右边界的坐标,分别。

这些段以任意顺序给出。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot10^5$$$。

输出

打印 $$$t$$$ 整数 — 按输入顺序给出给定测试用例 $$$t$$$ 的答案。如果删除任何给定的 $$$n$$$ 段,答案是 $$$n-1$$$ 段的并集中的最大段数。

示例

输入 #1

3
4
1 4
2 3
3 6
5 7
3
5 5
5 5
5 5
6
3 3
1 1
5 5
1 5
2 2
4 4

输出 #1

2
1
5