在间隔列表中搜索间隔重叠？

Question

假设[a,b]表示从a到b的实线上的间隔,a <b,包括(即,[a,b] =所有x的集合,使得a <= x <= b).另外,如果[a,b]和[c,d]共享任何x使得x在[a,b]和[c,d]中都是'重叠'.

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

显然,我可以尝试每个并在O(n)中得到它.但是我想知道我是否能够以一种聪明的方式对间隔列表进行排序,我可以通过二分搜索在O(log N)中找到/ one /重叠项目,然后从列表中的那个位置"环顾四周"找到所有重叠的间隔.但是,如何对间隔进行排序以使这种策略有效？

请注意,列表项中的元素之间可能存在重叠,这使得这很难.

我已经通过左边,右端,中间的间隔排序来尝试它,但似乎都没有导致详尽的搜索.

救命？

Answer 1

为了完整起见,我想补充说,这种问题有一个众所周知的数据结构,已知(惊讶,惊讶)作为间隔树.它基本上是一个增强的平衡树(红黑色,AVL,你的选择),它存储按左(低)端点排序的间隔.增强是每个节点在其子树中存储最大的右(高)端点.此树允许您在O(log n)时间内查找所有重叠间隔.

它在CLRS 14.3中有所描述.

Answer 2

[a,b]与[x,y]重叠iff b> x和a <y.按第一个元素对间隔进行排序可以为您提供与日志时间中第一个条件匹配的间隔.按最后一个元素对间隔进行排序可为您提供与日志时间中第二个条件匹配的间隔.取结果集的交叉点.