What is the most efficient way to validate an array of quantity ranges?

Question

Let's say I have an array of quantity ranges:

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

What is the most efficient way to validate that the ranges do not overlap (the above would fail validation)?

Answer 1

An obvious way is using an interval tree and inserting the items one by one. The checking would be trivial then.

Another approach would be more straightforward. You can sort the array lexicographically and maintain the leftmost available starting point. When a new interval comes, it must start after this point (we don't mind the gaps, because the array is sorted and the gap will never be accessed again).

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

Both of these run in O(N log N) time. I'm not sure if it can be done better.