在O(n)时间内计算重叠区间的数量？

Question

在O(n)时间内计算重叠区间的数量？

algorithmdata-structures

4

考虑一个由 (start, end) 组成的区间列表，这些区间已经按照它们的 start 分量在列表中排序。

我的问题是是否有一种方法可以计算每个不同的区间与之重叠的区间数，在 O(n) 时间内完成。

我想象了几个变体，可以在 O(n lg n) 时间内完成，但是我对 O(n) 约束很感兴趣。

例如，O(n lg n) 的解决方案如下：

1.将所有的 start 和 end 值添加到数组 A 中并对数组进行排序（现在我们处于 O(n lg n) 领域），在此过程中消除任何重复项。

2.从数组 A 创建一个区域数组 R（N-1 个区域，其中 R[i] = (A[i],A[i+1])）。

3.现在只需要遍历区间数组并增加其关联区域的值。这在 O(n) 中完成。

*好吧，如果我们知道区间在小区域内密集分布，我们可以使用计数排序，这会使我们回到 O(n)，但这似乎不是一种适用于一般情况的好假设。

有没有办法将此改进为 O(n)？

- devoured elysium

1

你很可能也需要对“end”点进行排序，因此“start”值已经排序并没有帮助到你。 - Niklas B.

似乎这应该放在http://cs.stackexchange.com/上。 - Erick G. Hagstrom

1

可以这样做，但我在这里看到了很多“Codility”风格的问题（200+），而在CS上却没有，所以我认为SO最终成为了这个问题更好的归属地。 - devoured elysium

2个回答

2

不使用基于比较的算法。（很可能这个论点可以扩展到固定度数的代数决策树，但那将使它变得更加技术化。）与排序一样，关键是要观察到，对于n!种输出可能性，我们不能比lg n！= Theta（n log n）比较更快，每个比较产生一个位（假设输入非退化，由于我们在这里讨论下限，因此在我们的控制之下，因此不是假设）。以下是编码/解码算法。（正式证明留作练习。）

Encoding: input is a1, ..., an such that aj in {1, ..., n + 1 - j}
          output is overlap counts c1, ..., cn of some instance

For j = 1 to n,
    Add an interval (j, j + aj - 1/2)
For j = 1 to n,
    Output the overlap count cj of the interval beginning at j

Decoding: input is overlap counts c1, ..., cn.
          output is a1, ..., an

For j = 1 to n,
    Initialize cj' = cj
For j = 1 to n,
    Set aj = cj' + 1
    For k = j + 1 to j + cj',
        ck' = ck' - 1

通过轻微修改，这个论点证明了阿米特算法在参数k上的渐进最优性。

- David Eisenstat

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

让每个间隔 i 表示为s_i，e_i（start_i，end_i）。

我可以展示算法，它的时间复杂度是O(nlogk)，其中k是与某些 i 相交的最大间隔数目，即区间（s_i，s_{i+1} ）。在最坏情况下，k是在O(n)中，但它确实提高了更分散间隔的性能。

我们将使用一个最小堆来存储间隔，同时迭代列表，最小堆将根据结束值(e_i)进行排序。

这个想法是通过升序开始迭代列表，计算被看到的间隔的数量，但是结束值却比间隔高。

伪代码(带有解释):

h = new min heap //sorted by end value
h.push (-infinity,infinity) //add a dummy interval for avoiding dealing with empty heap cases
res = 0
for each interval (s_i,e_i) in ascending order of s_i:
        //push out all already "expired" intervals:
        while (heap.min() < s_i):
            heap.pop()
        // at this point, all intervals in the heap:
        //    1. started before s_i
        //    2. finish after s_i
        // thus, each of them is intersecting with current interval.
        res = res + heap.size() - 1 //-1 for removing dummy interval (-inf,inf)
        heap.push(e_i)
return res

时间复杂度：

每个步骤中堆的大小最多为k(如上定义)。
每个区间只被推入和移除一次，每次操作的时间复杂度为O(logk)。
这样总的时间复杂度为O(nlogk)。

正确性：

声明：

两个区间(s_i,e_i)和(s_j,e_j)相交，当且仅当：

s_i <= s_j <= e_i   OR s_j <= s_i <= e_j

通过检查2个区间的所有可能性（由于 s_i<=e_i, s_j<=e_j，我们有 4!/(2!2!)=6 种可能性），证明很简单。

(1) s_i <= e_i <= s_j <= e_j           - no overlap
(2) s_j <= e_j <= s_i <= e_j           - no overlap
(3) s_j <= s_i <= e_i <= e_j           - overlap, and condition meets
(4) s_i <= s_j <= e_j <= e_j           - overlap, and condition meets
(5) s_j <= s_i <= e_j <= e_i           - overlap, and condition meets
(6) s_i <= s_j <= e_i <= e_j           - overlap, and condition meets

回到证明:

因此，我们知道如果两个区间相交，在遇到第二个区间（假设为(s_i,e_i)）时，第一个区间(s_j,e_j)仍然在堆中，因为s_i <= e_j，并且我们将(s_i,e_i)与(s_j,e_j)的交集添加到计数中。我们知道这也是正确的插入，因为我们已经看到了s_j，所以我们知道s_j <= e_j <= s_i，根据上述声明-这确实是一个相交的区间。

此外，由于对于每个相交的区间(s_i,e_i)和(s_j,e_j)，我们保证在处理(s_i,e_i)时(s_j,e_j)仍然在堆中（来自上述声明，并且因为我们永远不会将其删除，因为对于每个k我们已经处理：s_k <= s_i <= e_j -> e_j >= s_k），因此当我们在第二个区间遍历中添加堆的大小时，保证将计算(s_j,e_j)和(s_i,e_i)的交集。

证毕

小假设：不确定这是否能处理重复，应该通过仔细查看<和<=比较来处理这些边缘情况。

Python代码：

intervals = [(0,3.5),(1,2),(1.5,2.5),(2.1,3),(4,5)]
#5 overlaps
def findNumOverlapping(intervals):
    import heapq
    h = []
    heapq.heappush(h, 10000) #infinity
    res = 0
    for (s,e) in intervals:
        while (heapq.nsmallest(1, h)[0] < s):
            heapq.heappop(h)
        res = res + len(h) - 1
        heapq.heappush(h,e)
    return res