python - 在python中查找给定范围集之间的交集总数

Question

计算一组给定范围的交叉点数的最佳方法是什么。

例如:考虑范围对列表[start,stop]

[[1,5], [3,7], [9,11], [6,8]]

这里一共有2个路口，

[1,5] 与 [3,7] 相交

并且 [3,7] 与 [6,8] 相交

Answer 1

这个问题可以在 nlogn 时间内完成，当然你可以在 n^2 内完成，但听起来你希望它的时间最优。

我将这些间隔称为重叠，这是一个经典，您会在许多访谈书籍中找到它的变体。方法如下:

1. 按开头对项目进行排序。
2. 现在逐步浏览这些项目。为它结束的每个项目存储一个最小堆，成本 nlogn 但没关系，我们已经支付了。在每个新的起始编号处，您都知道有多少先前的交叉点重叠。删除您已经跑完的间隔。

由于搜索而最终成为 nlogn，这与您随后在 n 时间内逐步完成无关紧要。

例子:

1. 排序为 [1, 5], [3, 7], [6, 8], [9, 11]
2. 存储一个表明它在 5 处结束的堆项。
3. 进入第二个项目。堆的大小为 1，因此将重叠计数加 1。将 7 添加到堆中。
4. 开始第三项。从堆中删除 5。留下 7，所以再次加 1。将 8 添加到堆中。
5. 找到第 4 个项目，放下第 7 个和第 8 个，留下一个空堆。结果是 2。

import heapq
import operator

def mysol(v):

    overlaps = 0
    minheap = []

    vsorted = sorted(v, key=operator.itemgetter(0))

    for i in range(len(vsorted)):
        while len(minheap) > 0 and minheap[0] < vsorted[i][0]:
            heapq.heappop(minheap)

        overlaps += len(minheap)
        heapq.heappush(minheap, vsorted[i][1])

    return overlaps