在间隔列表中search间隔重叠？
说[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]，…），find与[x，y]重叠的所有区间的最有效方法是什么？
显然，我可以尝试每一个，并在O（n）。 但是我想知道是否可以用一些聪明的方式对间隔列表进行sorting，我可以通过二进制search在O（log N）中find/一个/重叠的项目，然后从列表中的位置“查找”来查找所有重叠的间隔。 但是，如何分类间隔以使这种策略起作用呢？
请注意，列表项本身中的元素之间可能会有重叠，这使得这很难。
我已经尝试了通过左端，右端，中间间隔sorting，但没有一个导致彻底search。
帮帮我？
[a，b]与[x，y]重叠，如果b> x且a <y。 按照它们的第一个元素对间隔进行sorting，可以使您在日志时间内匹配第一个条件。 按照最后一个元素对间隔进行sorting，可以使您在日志时间内与第二个条件匹配。 采取结果集的交集。
为了完整起见，我想补充一点，有一个众所周知的数据结构，就是这样的问题，已知（惊喜，惊喜）作为间隔树 。 它基本上是一个增强的平衡树（红黑色，AVL，你的select），存储按左（低）端点sorting的时间间隔。 增强是每个节点在其子树中存储最大的右（高）端点。 此树允许您在O（log n）时间查找所有重叠区间。
这在CLRS 14.3中有描述。
“四叉树”是一种常用于提高二维碰撞检测效率的数据结构。
我想你可以想出一个类似的一维结构。 这将需要一些预先计算，但应该导致O（log N）性能。
基本上，你可以从一个根节点开始，它覆盖了所有可能的时间间隔，当你添加一个节点到树中时，你决定是否落在中点的左边或右边。 如果它跨越中点，则将其分成两个区间（但是logging原始父区域）并从那里recursion地进行。 您可以对树的深度设置一个限制，这可以节省内存并提高性能，但代价是让一些事情复杂化（您需要在节点中存储一系列时间间隔）。
然后在检查一个区间时，基本上find插入的所有叶子节点，插入它们，检查这些节点内的部分区间是否相交，然后将logging的时间间隔作为“原始”父节点进行报告。
可以这么说，快速思考“袖口”。
你能把它们组织成2个列表，一个用于间隔开始，另一个用于间隔结束。
这样，您可以将y与间隔列表开头的项目（比如二进制search）进行比较，以此为基础减less候选项目。
然后可以将x与间隔列表末尾的项目进行比较。
编辑
案例：一旦closures
如果你只是在一次性的情况下比较间隔列表中的单个间隔，我不认为sorting会帮助你， 因为理想sorting是O（n） 。
通过对所有x进行线性search来修剪任何不可能的间隔，然后对剩余的y进行另一个线性search，可以减less您的总体工作量。 虽然这仍然是O（n），没有这个，你会做2n比较，而平均来说，你只会这样做（3n-1）/ 2比较。
我相信这是最好的，你可以做一个未sorting的名单。
案例：预先sorting不算
如果您将重复比较单个时间间隔和这个时间间隔列表，并对列表进行预先sorting，您可以获得更好的结果。 上面的过程仍然适用，但是通过在第一个列表上进行二分search，那么第二个可以得到O（m log n）而不是O（mn），其中m是被比较的单个间隔的数量。 请注意，仍然可以减less总体比较的优势。 [2m log n与m（3（log n）-1）/ 2相比较]
您可以同时按左端和右端进行sorting，并使用两个列表来消除没有重叠的值。 如果列表按左端sorting，那么testing范围右端右侧的间隔都不会重叠。 如果列表按右端sorting，那么testing范围左端左侧的间隔都不会重叠。
例如，如果间隔是
[1,4], [3,6], [4,5], [2,8], [5,7], [1,2], [2,2.5] 你会发现与[3,4]重叠，然后按左端进行sorting，并在testing的右端标记位置（右端刚刚大于其值，使得4包含在范围内）
[1,4], [1,2], [2,2.5], [2,8], [3,6], [4,5], *, [5,7]
你知道[5,7]不能重叠，然后通过右端和testing左端的标记位置进行sorting
[1,2], [2,2.5], *, [1,4], [4,5], [3,6], [5,7], [2,8]
你知道[1,2]和[2,2.5]不能重叠
不知道这将是多么高效，因为你必须做两种sorting和search。
正如您在其他答案中所看到的，大多数algorithm都与特殊的数据结构结合在一起。 例如，对于未分类的间隔列表，inputO(n)是最好的。 （通常从数据结构的angular度来考虑这个algorithm是比较容易的）。
在这种情况下，你的问题并不完整：
-
你给了整个清单还是你真的创造了它？
-
你只需要执行一个这样的查找或其中的许多？
-
你对它应该支持的操作和频率有什么估计吗？
例如，如果您只需要执行一次这样的查找，那么就不值得对之前的列表进行sorting。 如果很多，那么更昂贵的分拣或生成“一维四叉树”将被摊销。
然而，要解决这个问题是很困难的，因为一个简单的四叉树（就我所知）只能检测到碰撞，但不能创build与input重叠的所有段的列表。
一个简单的实现将是一个有序的（coordonate）列表，您可以在其中插入标记开始/结束和段号的所有段结束。 通过这种方式，通过parsing它（仍然是O（n），但是我怀疑如果你还需要所有重叠段的列表，可以使它更快），并且保持所有打开的段在“检查点“。
- C ++程序join重叠区间
- 使用合并sorting
- 样例invervals：（8，9）; （3,4）; （2，5）; （1,2）; （6,7）
- 答案：（1，5）; （6,7）; （8,9）
- 要求：start <end，即（6,5）不是有效的时间间隔
看代码
