在 O(nlog(n)) 中查找 "maximum" 重叠区间对

Question

问题陈述

输入一组 n 个间隔； {[s_1,t_1],[s_2,t_2],...,[s_n,t_n]}.

输出一对区间； {[s_i,t_i],[s_j,t_j]}，在所有间隔对中重叠 maximum。

例子

输入间隔：{[1, 10], [2, 6], [3,15], [5, 9]}

-> 可能有 6 个区间对。在这些对中，[1,10] & [3,15] 的最大可能重叠为 7.

输出：{[1,10],[3,15]}

朴素算法将是一种蛮力方法，其中所有 n 个间隔相互比较，同时跟踪当前最大重叠值。对于这种情况，时间复杂度为 O(n^2)。

我能够找到许多关于间隔树、最大重叠间隔数和最大集合的程序非重叠间隔，但没有关于这个问题。也许我可以使用上述算法中给出的想法，但我无法想出一个。

我花了很多时间试图找出一个好的解决方案，但我认为此时我需要一些帮助。

任何建议都会有所帮助！

Answer 1

首先，对间隔进行排序：首先按左端点按升序排列，然后——作为次要标准——按右端点按降序排列。对于此答案的其余部分，我假设间隔已经排序。

现在，最大可能重叠有两种可能性：

它可能在它完全覆盖的一个区间和后面的区间之间。
它可能在一个间隔和下一个间隔之间没有完全覆盖。

我们可以通过迭代间隔在 O(n) 时间内涵盖这两种情况，并跟踪以下内容：

迄今为止我们看到的最大重叠，以及相关的间隔对。
我们看到的最新间隔，称为 L，它的任何前辈都没有完全涵盖。（对此，关键的见解是，由于区间的排序，我们可以很容易地判断一个区间是否完全被它的任何前辈覆盖——因此我们是否需要更新 L — 通过简单地检查它是否完全被当前 L 覆盖。所以我们可以在 O(1) 时间内保持 L 最新.)

并计算每个区间与 L 的重叠。

所以：

result := []
max_overlap := 0
L := sorted_intervals[1]
for interval I in sorted_intervals[2..n]:
    overlap := MIN(L.right, I.right) - I.left
    if overlap >= max_overlap:
        result := [L, I]
        max_overlap := overlap
    if I.right > L.right:
        L := I

所以总成本就是对区间进行排序的成本，很可能是O(n log n)时间但是可能是 O(n) 如果你可以使用桶排序或基数排序或类似的。

在 O(nlog(n)) 中查找 "maximum" 重叠区间对

Finding "maximum" overlapping interval pair in O(nlog(n))

sorting

algorithm

search

intervals