描述
给一个数轴上的 $n$ 条线段,第 $i$ 条覆盖了 $[l_i, r_i]$(如果 $l_i = r_i$ 的话就是一个点)。一个线段集的 并集 是一个与原线段集所覆盖点一样的线段集,例如 $n = 5$,$5$ 条线段分别为 $[1,2]$,$[2,3]$,$[4,5]$,$[4,6]$,$[6,6]$,那么它们的 并集 就是 $[1,3]$ 和 $[4,6]$ 两条线段。现在,你要求出 正好删去一条线段后,并集 最多包括多少条线段。
如果两条线段重合,你依然只能删去一条。
输入
第一行是一个正整数 $t(1 \le t \le 10^4)$,表示数据组数。
每组数据的第一行是一个正整数 $n(2 \le n \le 2 \cdot 10^5)$,接下来 $n$ 行每行两个整数 $l_i, r_i(-10^9 \le l_i, r_i \le 10^9)$,含义如描述所示。
输出
对于每组数据输出一个数,表示 正好删去一条线段后,并集 最多包括多少条线段。
样例
输入
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输出
2
1
5解释
样例 1 解释:
- 删去 $[1,4]$,剩下 $[2,3]$,$[3,6]$,$[5,7]$,并集 大小为 $1$;
- 删去 $[2, 3]$,剩下 $[1, 4]$,$[3,6]$,$[5,7]$,并集 大小为 $1$;
- 删去 $[3, 6]$,剩下 $[1, 4]$,$[2, 3]$,$[5,7]$,并集 大小为 $2$;
- 删去 $[5, 7]$,剩下 $[1, 4]$,$[2, 3]$,$[3, 6]$,并集 大小为 $1$。
故输出为 $2$。
CodeForces 1285E Delete a Segment
原文:https://www.cnblogs.com/syksykCCC/p/CF1285E.html