Given 2 disjoint sets of intervals, find the intersections def getIntersection(set_item1, set_item2):
    (l11, l12) = set_item1
    (l21, l22) = set_item2
    if (l11 &gt; l21 and l11 &lt; l22) or (l12 &gt; l21 and l12 &lt; l22) or (l21 &gt; l11 and l21 &lt; l12) or (l22 &gt; l11 and l22 &lt; l12):
        if l11 &gt; l21:
            start = l11
        else: start = l21

        if l12 &gt; l22:
            end = l22
        else:
            end = l12
        return (start ,end)
    return None

def returnInersection(set1, set2):
    for l1 in set1:
        for l2 in set2:
            ret = getIntersection(l1, l2)
            if ret:
                print ret


I think above one works fine but it runs in O(n2). Is there any better solution?

Example input can be set1=[(1, 6), (10, 15), (20, 30)] and set2=[(2, 5), (7, 13)].
borrowing for Oscar Smith's solution

If the intervalsX are ordered, you can simply use:

def return_intersections(intervals1, intervals2):
    iter1 = iter(intervals1)
    iter2 = iter(intervals2)

    interval1 = next(iter1)
    interval2 = next(iter2)

    while True:
        intersection = getIntersection(interval1, interval2)
        if intersection:
            yield intersection
            try:
                if intersection[1] == interval1[1]:
                    interval1 = next(iter1)
                else:
                    interval2 = next(iter2)
            except StopIteration:
                return

        try:
            while interval1[0] &gt; interval2[1]:
                interval2 = next(iter2)
            while interval2[0] &gt; interval1[1]:
                interval1 = next(iter1)
        except StopIteration:
            return



list(return_intersections(set1, set2))



[(2, 5), (10, 13)]


in Python pre-3.5 all the try-except boilerplate wouldn't be necessary, but pep-476 changed this.

The advantage of this is that it works for any stream of ordered intervals. So intervalsX can be a generator, list, tuple,...