algorithm - 计算 O(n) 时间内的重叠间隔数？

Question

考虑 (start, end) 形式的间隔列表。间隔已按其 start 组件在列表中排序。

我的问题是，是否有一种方法可以在 O(n) 时间内计算每个不同的间隔，有多少间隔会与其重叠。

我设想在 O(n lg n) 时间内工作的几个变体，但我对 O(n) 约束感到好奇。

例如，O(n lg n) 解决方案是:

1. 将所有 start 和 end 值添加到数组 A 中并对数组进行排序(所以我们现在在 O(n lg n) realm*), 消除过程中的任何重复。
2. 从该数组 A 创建区域数组 R(N-1 个区域 R[i] = (A[i], A[i +1])).
3. 现在只需遍历间隔数组并增加所有关联区域的值即可。这是在 O(n) 中完成的。

*好吧，如果我们知道间隔密集地分布在一个小区域中，我们可以使用计数排序，这将使我们回到 O(n) 但这看起来不像对一般情况的一个很好的假设。

有什么方法可以将其改进为O(n)？

Answer 1

让每个区间i表示为s_i,e_i (start_i,end_i).

我可以展示一个算法，它是 O(nlogk) ，其中 k是与 (s_i,s_{i+1}) 相交的最大间隔数- 对于一些 i .
虽然在最坏的情况下，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 个区间的所有可能性证明很简单(自 4!/(2!2!)=6 以来我们有 s_i<=e_i, s_j<=e_j 可能性)

(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_j,e_j)处理时仍在堆中 (s_i,e_i) (根据上面的说法，因为我们永远不会删除它，因为对于每个 k 我们已经处理过:s_k <= s_i <= e_j -> e_j >= s_k)，保证 (s_j,e_j) 的交集和 (s_i,e_i)会在我们第二次区间遍历时加上堆的大小时被统计。

QED

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

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