寻找最长重叠时间间隔对

Question

假设我有一个包含n个整数区间[a,b]的列表，每个区间代表一个集合S = {a,a+1, ...b}。重叠是指|S_1 \ cap S_2|。例如：[3,6]和[5,9]在[5,6]上重叠，因此长度为2.任务是使用递归而不是动态规划，在Little-O(n^2)中找到具有最长重叠的两个区间。

显然，朴素方法是暴力破解，这并不符合时间复杂度条件。我也试过扫描线算法和/或最长公共子序列算法，但没有成功。

我无法想出将其分成子问题的方法。任何想法都会受到赞赏。

还发现了这个，我的看法是根本行不通： 在O(nlog(n))中找到“最大”重叠区间对

- Andrej Kováč

---

如果问题是关于寻找算法而不是实现它，也许[cs.se]更适合？（但请记住不要跨贴，在提问之前阅读他们的帮助中心） - user202729

仅仅说“在我看来根本不起作用”并不能证明它实际上不起作用。你需要解释为什么它不起作用，以及为什么你的问题不是重复的。 - user202729

暴力算法的时间复杂度为O(n^2)，因此它应该能够满足问题要求。 - Mitch

@Mitchel0022，请看一下小o符号和大O符号的区别。 - Andrej Kováč

Answer 1

这里有一种时间复杂度为 N log(N) 的方法。

将每个区间 [a,b] [c,d] 分解成这样的一组数对数组：

pair<a,-1>
pair<b,a>
pair<c,-1>
pair<d,c>

sort these pairs in increasing order. Since interval starts are marked as -1, in case of ties interval they should come ahead of interval ends.

for i = 0 to end of the pair array
    if current pair represents interval start
        put it in a multiset
    else
        remove the interval start corresponding to this interval end from the multiset.
        if the multiset is not empty
            update the maxOverlap with (current_interval_end - max(minimum_value_in_multiset,start_value_of_current_interval)+1)

这种方法应该将maxOverlap更新为最大可能的值。

- Obaida.Opu

Answer 2

保留关于两个最大重叠区间max1和max2的信息（一开始为空）。

按照x值对输入列表[x1, y1] .. [xn, yn]=I1..In进行排序，如果遇到相等的情况，则丢弃较短的区间。在丢弃区间的同时，保持max1和max2更新。

对于每个区间，在线性时间内添加一个属性max，显示已排序列表中所有前面区间的最大y值：

rollmax = −∞
for j = 1..n do
  Ij.max = rollmax
  rollmax = max(rollmax, Ij.y)

在已排序、过滤和扩展的输入列表上执行以下查询。它使用一个不断扩展的区间子列表，作为递归函数 SearchOverlap 的输入，该子列表小于当前搜索的区间 Ii。

for i = 2..n do
  SearchOverlap(Ii, 1, i − 1)
return {max1, max2}

SearchOverlap 函数使用 分治法 遍历排序列表 Il, .. Ir。它将这样的列表想象成一个完整的二叉树，其中间隔 Ic 是其本地根。测试 Ic.max < I.max 用于始终决定沿着与 I 有最大重叠的间隔方向遍历二叉树（向左/向右）。请注意，I 是查询的间隔，它与 log(n) 其他间隔进行比较。还要注意，在这样的遍历中可能会传递最大可能的重叠间隔，因此需要在函数 SearchOverlap 的开头检查最大重叠。

SearchOverlap(I , l, r)
c = ceil(Avg(l, r)) // Central element of queried list
if Overlap(max1, max2) < Overlap(I , Ic) then
  max1 = I
  max2 = Ic
if l ≥ r then
  return
if Ic.max < I.max then
  SearchOverlap(I , c + 1, r)
else
  SearchOverlap(I , l, c − 1)
return

最大重叠区间（如果不为空）将在最后返回。总复杂度为O(n log(n))。

- Kupto