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

Question

假设我有一组数量范围:

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

验证范围不重叠的最有效方法是什么(上述方法将无法验证)？

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) 时间内运行。我不确定是否可以做得更好。