algorithm - 从间隔列表中有效地找到重叠间隔

Question

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

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

结果应该是

[2,3], [7,8]

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

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

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

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

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

Answer 1

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

对于您的示例，过渡将是:

[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。哪个是答案。

创建一个长列表和排序的想法是公认的额外工作。您可以改为创建这些列表并即时合并它们。节省是序列数的对数而不是事件数的对数的一个因素。