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.