首页 > 其他 > 详细

CodeForces 1285E Delete a Segment

时间:2020-01-13 19:40:54      阅读:133      评论:0      收藏:0      [点我收藏+]

Description CodeForces 1285E

描述

给一个数轴上的 $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$。

Solution

CodeForces 1285E Delete a Segment

原文:https://www.cnblogs.com/syksykCCC/p/CF1285E.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!