验证数量范围数组的最有效方法是什么？

Question

假设我有一个数量范围的数组：

[{min=1, max=500}, {min=2, max=1000}, ...]

什么是验证范围不重叠的最有效方法（上述内容将无法通过验证）？

- Eric Belair

Answer 1

一种明显的方法是使用区间树，逐个插入项目。然后检查将会很简单。

另一种方法更加直接。您可以按字典顺序对数组进行排序，并保持最左侧可用起始点。当出现新的区间时，它必须在此点之后开始（我们不介意间隙，因为数组已排序，而且永远不会再次访问该间隙）。

def validate(listoftuples):
    rightedge = -10000000000000000 # some kind of minus infinity
    listoftuples.sort()
    valid = True
    for l, r in listoftuples:
        if l >= rightedge:
            rightedge = r
        else:
            valid=False
            break
    return valid

validate([(1, 500), (2, 1000)]
>>> False
validate([(1, 2), (2, 1000)])
>>> True

这两个运行时间都是 O(N log N)。我不确定是否有更好的方法。

- Danstahr

---

优秀的解决方案。谢谢。 - Eric Belair