在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]}。 输入 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]}。

一个朴素的算法是暴力枚举所有的区间并比较它们之间的重叠程度，同时跟踪当前最大的重叠值。这种情况下的时间复杂度是O(n^2)。

我发现了很多关于“区间树”、“最大重叠区间数”和“最大不重叠区间集”的算法，但没有找到解决这个问题的方法。也许我可以使用上述算法中提供的思路，但是我自己没有想出来。

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

任何建议都会有所帮助！

- user1751434

---

这个问题可以使用扫描线算法在O(nlogn)的时间复杂度内解决。 - Saeid

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)。

- ruakh

---

你是个天才。 - user1751434

不适用于区间(1,6),(3,6),(5,8)。根据您的逻辑，我们将忽略(3,6)，因为它被其前任(1,6)覆盖。我们剩下(1,6),(5,8)，它们之间的重叠=1。这是错误的，因为最大重叠在(1,6),(3,6)之间=3。 - user3886907

@user3886907：哎呀，你说得很对，谢谢！我会修复的…… - ruakh

@dixitk13：绝对不是，因为解决这个问题的任何算法都需要检查所有的区间。 - ruakh

@dixitk13：我觉得你没有考虑构建增强区间树的时间？ - ruakh