查找一组重叠的间隔 [英] Finding intervals of a set that are overlapping

问题描述

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

So I have a set containing the endpoints of intervals. For example,

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

我需要一种方法找出有多少重叠的时间间隔。在上述情况下，答案为5，因为

I need a way to find out how many overlapping intervals are there. In the above case, the answer would be 5 since

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

我需要一个采用 O（N log N）时间来找出总和。现在，如果我对所有起点进行排序并在每个点上应用此处建议的答案查找数字范围交点我得到一个O（N ^ 2）解决方案。除集合外，我可能还需要什么样的数据结构的任何线索？

I need an algorithm that takes O(N log N) time to find out the sum. Now if I sort all the starting points and apply the answer suggested here on every point Find number range intersection I get an O(N^2) solution. Any clue on what kind of data structure I might need in addition to a set? Thanks!

推荐答案

为每个间隔[a，-1]生成值（a，-1），（b，1）的列表。 b]。现在，对它们进行排序可以让您遍历数组，仅通过合计+1和-1s就可以计算出每个端点当前打开了多少间隔。

Build a list of values (a, -1), (b, 1) for every interval [a, b]. Now sorting these lets you run through the array, counting how many intervals are currently open at each endpoint, just by aggregating the +1 and -1s.

重要的是（ b，1）在排序列表中的（b，-1）之后；因为即使相交在单个点，我们也要计算相交。

It's important that (b, 1) comes after (b, -1) in the sorted list; because we want to count the intersection even if the intersection is at a single point.

在此处完成代码。

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），不需要任何花哨的数据结构。

Note, this is trivially O(n log n), and doesn't need any fancy data-structures.

这篇关于查找一组重叠的间隔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！