algorithm - 查找重叠的集合的间隔

Question

所以我有一个包含区间端点的集合。例如，

Set s = {(1,4),(3,7),(5,8),(14,17),(0,2),(11,14)}

我需要一种方法来找出有多少重叠间隔。在上面的例子中，答案是 5，因为

(1,4) --> (3,7), (0,2)
(3,7) --> (5,8),(0,2)
(5,8) --> 
(14,17) --> (11,14)

我需要一种算法，它需要花费 O(N log N) 时间来找出总和。现在，如果我对所有起点进行排序并在每个点上应用此处建议的答案 Find number range intersection我得到一个 O(N^2) 解决方案。关于除了集合之外我可能需要哪种数据结构的任何线索？谢谢!

Answer 1

为每个区间 [a, b] 构建一个值列表 (a, -1), (b, 1)。现在对这些进行排序让您可以遍历数组，计算每个端点当前打开的间隔数，只需聚合 +1 和 -1。

重要的是 (b, 1) 在排序列表中出现在 (b, -1) 之后；因为即使交点在单个点，我们也想计算交点。

在这里完成代码。

def overlaps(intervals):
    es = []
    for a, b in intervals:
        es.append((a, -1))
        es.append((b, 1))
    es.sort()
    result = 0
    n = 0
    for a, s in es:
        if s == -1: result += n
        n -= s
    return result

请注意，这很简单 O(n log n)，并且不需要任何花哨的数据结构。