从间隔列表中有效查找重叠间隔

这与查找重叠间隔有关。我知道如何给定一个间隔列表（间隔树）。我所拥有的是间隔列表。例如，从间隔列表中有效查找重叠间隔

[2,6], [7,11] 
[1,3], [5,10], [11,13] 
[2,5], [6,8]

这个结果应该是

[2,3]，[7,8]

我需要做的是找到所有列表中常见的间隔列表。

我看到此问题与合并n列表类似。问题是我无法应用列表的成对合并。应用此方法会导致重叠间隔的丢失。所以我需要将所有列表合并在一起考虑所有列表（而不是成对）。

我可以使用区间树。将每个列表的第一个区间插入到区间树中并找到重叠区域。从树中删除最薄弱的时间间隔，并从其中一个列表中插入下一个时间间隔。我还没有完全想到如何使用这种方法，但似乎它会变得太昂贵。

是否有任何有效的算法来从间隔列表中查找重叠间隔。

附加信息： 列表中的间隔进行排序。它们不重叠并形成一个序列。

来源

2013-08-22 akaHuman

创建单个排序的转换数组。根据您加入或离开的时间间隔，每个转场都有一个位置和一个累计数字。当你通过列表时，记住你有多少个间隔。当你处于一系列的间隔时，就是你处于一个常见的间隔时间。

对于示例的过渡将是：

[2, 1], [6, -1], [7, 1], [11, -1], 
[1, 1], [3, -1], [5, 1], [10, -1], [11, 1], [13, -1] 
[2, 1], [5, -1], [6, 1], [8, -1]

其按位置排序和合并崩溃后：

[1, 1], [2, 2], [3, -1], [5, 0], [6, 0], [7, 1], [8, -1], [10, -1], [11, 0], [13, -1]

，让你转换运行的总计：

[1, 1], [2, 3], [3, 2], [7, 3], [8, 2], [10, 2], [13, 1]

然后我们可以读取我们在3的时间间隔，从一开始2并且去到3，另一个从7开始并且去到8。这是答案。

创建一个长列表和排序的想法无疑是额外的工作。您可以创建这些列表并将它们即时合并。节省量是系列数量的日志的一个因素，而不是事件数量的日志。

来源

2013-08-22 07:38:46 btilly

很抱歉，我失去了你在“这给你跑转总数”。你能否详细说明一下。谢谢！ – akaHuman

第一个条目仍然是位置。第二个是这一点的变化总和。所以我们开始'[1,1]'，然后'[2,1 + 2]'，然后'[2,1 + 2-1]'等等（因为变化遵循'1,2，-1， 0，0，1，-1，-1,0，-1'）。 0转换并不重要，所以我放弃了它们。 – btilly

谢谢！这是一个很好的。 – akaHuman

我对你想要做什么的理解是在区间列表上应用交集操作。你可以做成这样两两交叉是相关联的。

我会做的是一样的东西

Let S be the set of sets, R = s1, s1 in S 
    for each set s2 in S/{s1} 
       for each element e1 in R 
        for each element e2 in s2 s.t. e1.sup < e2.inf 
        e1 <- intersection (e1, e2)

两个间隔之间的交集操作

intersection (e1,e2): 
    return new Interval(max(e1.inf, e2.inf), min (e1.sup, e2.sup));

来源

2013-08-22 07:56:05 hpid91

这是我猜的蛮力解决方案！如果我能找到一个更高效的解决方案，我期待着。 – akaHuman

是的，它是O（n）。如果你的集合是有序的，那么你可以在平均情况下做得更好（当你遇到一个元素e2，只要第二个元素的下界优先于第二个元素的上界就可以跳出第二个循环，只需编辑伪代码即可。 – hpid91

你说的间隔中的每个单独的列表进行排序和非重叠。所以，

Keep track of where you are in each list, starting at the beginning of each. 
While none of the lists has run out: 
    If the current intervals (one from each list) all overlap: 
     Output the intersection of the current intervals 
    Find which of the current intervals has the earliest end point 
    Advance one position within that list.

如果有时间间隔和N个区间共K个清单，如果以最简单的方式实现，但是你应该能够将这一数字减少至O应该采取O（NK）时间（N日志K）时间，方法是跟踪有关堆或其他优先级队列中当前时间间隔的信息。

来源

2013-08-22 15:31:06

从间隔列表中有效查找重叠间隔

回答

相关问题