Fast way to check if a region overlaps another (1-d) region

I have a huge set of regionssically thousands of points with a start and an end. I.e.:

[(3015, 3701), (4011, 5890), ....]

I also have another set of points (both start and end) where I want a quick way to test whether or not a region in this set overlaps a region in the other set. Is there a fast way to do this?

Thanks!

--EDIT--

@Spike Gr开发者_Python百科onim answered my question with an Interval Tree.

Thanks, Spike!

http://en.wikipedia.org/wiki/Interval_tree

def test(lista, listb):
    a = 0
    b = 0
    found = False
    while a<len(lista) and b<len(listb):
        result = check( lista[a] , listb[b] )
        if result < 0:
            a += 1
            continue
        if result > 0:
            b += 1
            continue
        # we found overlapping intervals
        found = True
        return (found, a, lista[a], b, listb[b] )
    return found

def check( (astart, aend) , (bstart, bend) ):
    if aend < bstart:
        return -1
    if bend < astart:
        return 1
    return 0


lista = [(3015, 3701), (4011, 5890)]
listb = [(1,2), (100,200), (4500,6000)]
result = test(lista, listb)
print result

Find the min/max endpoints of both regions then see if those overlap.