Is there a standard Python data structure that keeps things in sorted order?

It looks like you want something like bisect’s insort_right/insort_left. The bisect module works with lists and tuples.

import bisect

l = [(0, 100), (150, 300), (500, 1000)]
bisect.insort_right(l, (250, 400))
print l # [(0, 100), (150, 300), (250, 400), (500, 1000)]
bisect.insort_right(l, (399, 450))
print l # [(0, 100), (150, 300), (250, 400), (399, 450), (500, 1000)]

You can write your own overlaps function, which you can use to check before using insort.

I assume you made a mistake with your numbers as (250, 400) overlaps (150, 300).
overlaps() can be written like so:

def overlaps(inlist, inrange):
    for min, max in inlist:
        if min < inrange[0] < max and max < inrange[1]:
            return True
    return False