在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)时间,但如果您可以使用bucket-sort或radix-sort或类似的话,则可能是O(n).