在 O(nlog(n)) 中找到“最大”重叠区间对

Question

问题陈述

输入 n 个间隔的集合； {[s_1,t_1], [s_2,t_2], ... ,[s_n,t_n]}.

输出 一对间隔； {[s_i,t_i],[s_j,t_j]}，所有区间对之间具有最大重叠。

示例

输入区间：{[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) 时间或类似。

Answer 2

嗨呀！！嘿呀！！！嘿呀！！博亚啊！！嘿呀！！