← 返回题目列表

Codeforces · 1029/C

C. 最大交叉点

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

在数轴上给你 $$$n$$$ 线段;每个线段的每个端点都有整数坐标。有些段可以退化为点。线段可以相互交叉、相互嵌套甚至重合。

线段序列的交集是最大的点集(不一定具有整数坐标),使得每个点都位于序列中的每个线段内。如果结果集不为空,那么它总是形成一些连续的段。交集的长度是结果线段的长度,如果交集是空集,则为 $$$0$$$。

例如,线段 $$$[1;5]$$$ 和 $$$[3;10]$$$ 的交集是 $$$[3;5]$$$(长度 $$$2$$$),线段 $$$[1;5]$$$ 和 $$$[5;7]$$$ 的交集是 $$$[5;5]$$$(长度 $$$0$$$)并且交集段 $$$[1;5]$$$ 和 $$$[6;6]$$$ 是一个空集(长度 $$$0$$$)。

您的任务是从给定序列中恰好删除一个段,以使剩余 $$$(n - 1)$$$ 段的交集具有最大可能长度。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — 序列中的段数。

接下来的 $$$n$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$0 \le l_i \le r_i \le 10^9$$$) — 第 $$$i$$$ 段的描述。

输出

打印一个整数 — 从序列中删除一个片段后 $$$(n - 1)$$$ 剩余片段的交集的最大可能长度。

示例

输入 #1

4
1 3
2 6
0 4
3 3

输出 #1

1

输入 #2

5
2 6
1 3
0 4
1 20
0 4

输出 #2

2

输入 #3

3
4 5
1 2
9 20

输出 #3

0

输入#4

2
3 10
1 5

输出#4

7

注意

在第一个示例中,您应该删除线段$$$[3;3]$$$,交集将变为$$$[2;3]$$$(长度$$$1$$$)。删除任何其他线段将导致交集 $$$[3;3]$$$(长度 $$$0$$$)。

在第二个示例中,您应该删除线段 $$$[1;3]$$$ 或线段 $$$[2;6]$$$,交集将分别变为 $$$[2;4]$$$ (长度 $$$2$$$)或 $$$[1;3]$$$ (长度 $$$2$$$)。删除任何其他线段将导致交集 $$$[2;3]$$$(长度 $$$1$$$)。

在第三个示例中,无论您删除哪条线段,交集都将变为空集。

在第四个示例中,如果删除段 $$$[1;5]$$$,您将获得交集 $$$[3;10]$$$(长度 $$$7$$$);如果删除段 $$$[3;10]$$$,您将获得交集 $$$[1;5]$$$(长度 $$$4$$$)。