题目描述

难度分:$1600$

输入$n(2 \leq n \leq 3 \times 10^5)$和$n$条线段的左右端点$L[i]$，$R[i](0 \leq L[i] \leq R[i] \leq 10^9)$。

你需要删除恰好一条线段，使得剩下的$n-1$条线段的交集长度最大。输出最大长度。

• 例如$[1,5]$和$[3,9]$的交集为$[3,5]$，长度为$2$。
• 例如$[1,5]$和$[5,7]$的交集为$[5,5]$，长度为$0$。
• 例如$[1,5]$和$[6,6]$的交集为空，长度为$0$。

输入样例$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

算法

前后缀分解

感觉最近灵茶开始上难度，周二竟然就$1600$了，周四现在也经常$2000$、$2100$。这个题只要想到了所有区间公共部分的端点怎么求就很好做，不然就卡题。

假设输入的原始区间数组为$intervals$，维护$prel$、$prer$、$sufl$、$sufr$四个数组。$prel[i]$、$prer[i]$、$sufl[i]$、$sufr[i]$分别表示前缀$intervals[0…i]$中最大的左端点、最小的右端点，后缀$intervals[i…n-1]$中最大的左端点，最小的右端点。

当遍历到区间$i$时，考虑删除区间$i$后，所有区间的公共部分。此时所有剩余区间公共部分的左端点为$left=max(prel[i-1],sufl[i+1])$，右端点为$right=min(prer[i-1],sufr[i+1])$。遍历所有区间，维护$right-left$的最大值就行了。

复杂度分析

时间复杂度

预处理出两个$pre$数组和两个$suf$数组的时间复杂度是$O(n)$，枚举所有删除的区间$intervals[i]$的时间复杂度也是$O(n)$，所以算法的时间复杂度为$O(n)$。

空间复杂度

空间消耗的瓶颈就是两个$pre$数组和两个$suf$数组，都是线性的。因此，算法的额外空间复杂度为$O(n)$。

$python$代码

n = int(input())
intervals = []
for _ in range(n):
    l, r = map(int, input().split())
    intervals.append((l, r))
prel, prer, sufl, sufr = [intervals[0][0]]*n, [intervals[0][1]]*n, [intervals[-1][0]]*n, [intervals[-1][1]]*n
for i in range(1, n):
    j = n - 1 - i
    prel[i] = max(prel[i - 1], intervals[i][0])
    prer[i] = min(prer[i - 1], intervals[i][1])
    sufl[j] = max(sufl[j + 1], intervals[j][0])
    sufr[j] = min(sufr[j + 1], intervals[j][1])
ans = max(max(sufr[1] - sufl[1], 0), max(prer[-2] - prel[-2], 0))
for i in range(1, n - 1):
    l = max(prel[i - 1], sufl[i + 1])
    r = min(prer[i - 1], sufr[i + 1])
    ans = max(ans, max(r - l, 0))
print(ans)