4

这与寻找重叠区间有关。我知道如何在给出区间列表（区间树）的情况下这样做。我所拥有的是间隔列表。例如，

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

结果应该是

[2,3], [7,8]

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

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

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

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

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

4

3 回答 3

4

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

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

[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-22T07:38:46.477 回答
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));
于 2013-08-22T07:56:05.600 回答
2

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

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(NK) 时间，但是您应该能够通过跟踪有关当前的信息将其减少到 O(N log K) 时间堆或其他优先级队列中的间隔。

于 2013-08-22T15:31:06.083 回答