在区间列表中搜索重叠的区间？

Question

假设[a,b]表示实线上从a到b的区间，其中a＜b，包括两端点（即，[a,b]=所有满足a≤x≤b的x）。此外，如果存在x既属于[a,b]又属于[c,d]，则称[a,b]和[c,d]“重叠”。

给定一个区间列表（[x1,y1]，[x2,y2]，...），最有效的方法是什么，以找到与[x，y]重叠的所有这样的区间？

显然，我可以尝试每个区间并在O(n)时间内获得结果。但我想知道是否可以以某种巧妙的方式对区间列表进行排序，以便通过二分查找在O(log N)时间内找到/一个/重叠的区间，然后从该位置在列表中“向外搜索”，以找到所有重叠的区间。然而，如何对区间进行排序，使得这样的策略可行呢？

请注意，列表项本身可能存在重叠，这就使问题变得更加困难。

我尝试过按左端、右端、中心等对区间进行排序，但似乎没有一种能够导致完整搜索的排序方法。

有什么建议吗？

- cespinoza

---

+1 因为它使我的工作日更加有趣。 - Dan McGrath

Answer 1

为了完整起见，我想补充一下，针对这种问题有一个广为人知的数据结构，称为区间树（惊喜吧）。它基本上是一个增强平衡树（红黑树、AVL树，您随意选择），按其左端点（低点）排序存储间隔。增强部分是每个节点储存其子树中最大右端点（高点）。该树可以在O(log n)时间内找到所有重叠的区间。

CLRS 14.3中进行了描述。

- Ben

Answer 2

[a, b] 与 [x, y] 重叠当且仅当 b > x 且 a < y。通过按照首元素对区间进行排序，可以在对数时间内获取满足第一个条件的区间。通过按照末尾元素对区间进行排序，可以在对数时间内获取满足第二个条件的区间。取这些结果集的交集即可。

- gdj

---

如果列表长度为N，一个与列表中的查询间隔“相似大小”的查询区间将在第一个列表中产生m个匹配项，并在第二个列表中产生最多N-m个匹配项。 如果要执行交集操作，则需要遍历所有N个元素，因此交集操作的时间复杂度为O(n)。 - cespinoza

它需要O(匹配条件的较小列表的大小)。如果所有间隔中只有一小部分符合条件，比如f(N)，那么它需要O(f(N))。我假设这将是情况——否则我认为任何策略都大致需要O(N)。 - gdj

这不是最佳答案；你所描述的内容属于此页面上的“幼稚方法”：http://en.wikipedia.org/wiki/Interval_tree。事实上，另一个回答更正确地建议查看区间树。 - johnbakers

重叠检测条件需要使用 >= 和 <=。上面的答案与暴力方法（即 O(n)）具有相同的运行时间。 Corman 14.3节中介绍的区间树是您想要的。 - Shital Shah

@gdj 为什么需要 O(匹配条件的较小列表的大小) 的时间复杂度？难道不应该是 O(匹配条件的较大列表的大小) 吗？难道不需要遍历两个集合才能取交集吗？ - max

@max：遍历较小的集合；对于每个元素，检查它是否在较大的集合中（使用类似哈希表的东西进行常数成员查询）。 - Tom Church

Answer 3

'四叉树' 是一种经常用于提高二维碰撞检测效率的数据结构。

我认为你可以想出类似的一维结构。这将需要一些预计算，但应该会得到O(log N) 的性能。

基本上，您从覆盖所有可能间隔的根 '节点' 开始，当向树添加节点时，您决定它是在中点的左侧还是右侧。如果它跨越了中点，您就将其分成两个间隔（但记录原始父项）并从那里递归进行。您可以设置树的深度限制，这可以节省内存并提高性能，但代价是稍微复杂一些（您需要在节点中存储间隔列表）。

然后，在检查间隔时，您基本上找到将其插入的所有叶节点，检查这些节点中的部分间隔是否相交，然后将记录在它们中的间隔报告为“原始”父项。

- sje397

---

有趣的是，那种相似的结构被称为二叉树。 - Engineer

@Nick Wiggill - 这是一种二叉树类型，当然，二叉树有很多用途，我正在描述的算法更加详细。 - sje397

Answer 4

随便说一下我的想法。

你能不能把它们分成两个列表，一个是区间开始的列表，另一个是区间结束的列表。

这样，你就可以将 y 与区间开始列表中的项进行比较（例如通过二分查找），以此来缩小候选范围。

然后你可以将 x 与区间结束列表中的项进行比较。

编辑

情况：仅一次

如果你只是在一次性地将单个区间与区间列表进行比较，我认为排序不会帮助你因为理想排序的时间复杂度是O(n)。

通过对所有 x 进行线性搜索来排除任何不可能的区间，然后再通过剩余的 y 进行另一次线性搜索，可以减少总工作量。虽然这仍然是 O(n)，但如果不这样做，你将进行 2n 次比较，而平均而言，你只需要进行 (3n-1)/2 次比较。

我认为这是在未排序列表中所能做到的最好的。

情况：预排序不计算在内

在您需要反复将单个区间与该区间列表进行比较并对列表进行预排序的情况下，您可以获得更好的结果。上述过程仍然适用，但是通过在第一个列表上进行二分搜索，然后在第二个列表上进行二分搜索，您可以获得O(m log n)而不是O(mn)，其中m是要比较的单个区间的数量。请注意，这仍然使您减少了总比较次数的优势。[2m log n与m(3(log n)-1)/2相比]

- Dan McGrath

---

你在回答顶部的初始建议属于此页面上的“Naive approach”：en.wikipedia.org/wiki/Interval_tree。 - johnbakers

Answer 5

您可以同时按左端和右端进行排序，并使用两个列表来消除不重叠的值。如果列表按左端排序，则测试范围右端右侧的任何区间都不会重叠。如果列表按右端排序，则测试范围左端左侧的任何区间都不会重叠。

例如，如果区间为

[1,4], [3,6], [4,5], [2,8], [5,7], [1,2], [2,2.5]

如果你正在寻找与[3,4]重叠的部分，那么按左端排序并标记测试的右端位置（将右端设置为比其值略大，以便包括4在范围内）。

[1,4], [1,2], [2,2.5], [2,8], [3,6], [4,5], *, [5,7]

你知道[5,7]不能重叠，所以按右端点排序并标记测试的左端点位置

[1,2], [2,2.5], *, [1,4], [4,5], [3,6], [5,7], [2,8]

你知道 [1,2] 和 [2,2.5] 不能重叠

不确定这样做的效率如何，因为你需要进行两次排序和搜索。

- Nemo157

Answer 6

正如其他答案中所述，大多数算法都与特殊的数据结构一起使用。例如，对于未排序的区间列表作为输入，O(n) 是最好的结果（通常更容易从数据结构的角度思考算法）。

在这种情况下，您的问题不完整：

• 您是否已经拥有整个列表，还是需要自己创建它？

• 您只需要执行一个这样的查找，还是需要执行多个？

• 您是否对它应该支持的操作及其频率有任何估计？

例如，如果您只需要执行一个这样的查找，则在排序列表之前并不值得。如果需要执行多个，则更昂贵的排序或生成“1D四叉树”将被摊销。

然而，解决它可能会很困难，因为简单的四叉树（据我所知）仅能检测到碰撞，但无法创建与您的输入重叠的所有段的列表。

一个简单的实现方式是使用按坐标排序的列表，将所有带有起始/结束标志和段号的线段端点插入其中。通过解析它（仍然是O(n)，但如果您还需要重叠的所有线段列表，则我怀疑您无法使其更快），并跟踪在“检查点”未关闭的所有打开的线段。

- ruslik