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

Question

这与寻找重叠的间隔有关。给定一个间隔列表（间隔树），我知道如何做到这一点。我有一个间隔列表。例如，

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

结果应该是

[2,3], [7,8]

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

我认为这个问题类似于合并列表。问题是我无法应用列表的成对合并。应用此方法可能会导致丢失重叠间隔。因此，我需要将所有列表合并在一起，一次考虑所有列表（而不是成对）。

我可以使用间隔树。将每个列表中的第一个间隔插入间隔树并查找重叠部分。从树中删除最弱的间隔，并从其中一个列表中插入下一个间隔。我还没有完全弄清楚如何使用这种方法，但它似乎太贵了。

是否有任何有效的算法可以从间隔列表中找到重叠的间隔。？

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

Answer 1

您说过，每个单独的间隔列表都是经过排序且不重叠的。所以

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.

如果有K个间隔列表和N个间隔，如果以最直接的方式实现，这应该需要O（N K）时间，但您应该能够通过跟踪有关堆或其他一些优先级队列中当前间隔的信息来将其减少到O（N log K）时间。

Answer 2

我的理解是在区间列表上应用交集运算。你可以两两做，因为交集是关联的。

我会这样做

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));

Answer 3

创建一个单一的、排序的转换数组。每个转换都有一个位置，以及一个基于您要加入或离开的间隔数的累积数。当您通过列表时，请跟踪您处于多少个间隔中。当您处于与系列相同的间隔中时，那就是您处于公共间隔中的时候。

对于您的示例，转换将是：

[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。这就是答案。

诚然，创建一个长列表并进行排序的想法是额外的工作。您可以转而创建这些列表并动态合并它们。节省的费用是系列数量日志的因素，而不是事件数量日志的因素。