intersect.py

#Make sure your intervals are sorted
A = [(1,2), (5,6), (6,8), (8,10)]
B = [(2,3), (8,9), (11, 18)]

print "A =", A
print "B =", B
def intersects(a, b):
    start = max(a[0], b[0])
    end = min(a[1], b[1])
    return end - start >= 0

i = 0
j = 0
res = []

while i < len(A) and j < len(B):
    a = A[i]
    b = B[j]
    if not intersects(a, b):
        if a[0] < b[0]:
            i+=1
        else:
            j+=1
    else:
        res.append((i, j))
        if a[0] < b[0] or a[1] < b[1]:
            i+=1
        else:
            j+=1


print "------"
print "R =", res