algorithm - O(nlogn) 算法查找包含其他范围的范围

Question

如果你有 n 个范围，其中一个范围类似于 [1,4.5] ，你怎么能找到是否有任何索引包含另一个在 O(nlogn)时间？注:[x,y]将完全包含 [a,b]如果x >= a和 b <= y .

这似乎可以类似于合并排序来完成，您可以在其中检查范围总数的每一半中是否有任何范围包含另一个范围，然后比较任一范围中的任何范围是否包含另一半中的范围。我的问题是找不到 O(n)做这最后一部分的方法。我猜我必须以某种方式组合一些范围，但我想不出如何组合。

Answer 1

这是一个简单的算法，似乎在 O(nlogn) 时间内运行:

首先使用范围的开始值从最小到最大对 n 范围的集合进行排序。如果您在这里使用合并排序，这应该在 O(nlogn) 时间内运行。正如@Aivean 指出的那样，当两个或多个范围具有相同的起始值时，需要考虑一种边缘情况。在这种情况下，此类范围应按其范围结束值以降序顺序排列。

接下来沿着这组范围从最小的第一个值到最高的，并执行以下操作:

for (range r : ranges[1 to N-1]) {
    if (end value for range r+1 <= end value for range r) {
        // then range r+1 is completely contained within some previous range
        return true;
    }
}

第二步是单个 O(n) 遍，不会改变第一步的总体 O(nlogn) 运行时间。

这是一个向您展示该算法如何工作的图形说明。范围已使用范围的开始 值从小到大排序。应该清楚的是，所有必要的是从左到右遍历并按顺序比较每对范围的结束值。

1. |------|
2.  |-------|
3.    |-------|
4.    |------|
5.              |-------|
6.                  |-------|

请注意，在检查范围 #3 时，我们不需要检查超出范围 #2 的任何内容。这样做的原因是，为了让范围 #1 包含范围 #3，它必须扩展超出范围 #2，这意味着它已经包含范围#2。但这意味着算法已经返回 true，因此我们不需要检查这种可能性。

另请注意，范围#3 和#4 按其结束值降序排列。这确保算法将检测到范围#4 完全包含在范围#3 内。您可以颠倒范围 #3 和 #4 的顺序，看看在起始值相同的情况下可能会出现什么问题。