Given 2 disjoint sets of intervals, find the intersections

Question

def getIntersection(set_item1, set_item2):
    (l11, l12) = set_item1
    (l21, l22) = set_item2
    if (l11 > l21 and l11 < l22) or (l12 > l21 and l12 < l22) or (l21 > l11 and l21 < l12) or (l22 > l11 and l22 < l12):
        if l11 > l21:
            start = l11
        else: start = l21

        if l12 > 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(n²). Is there any better solution?

Example input can be set1=[(1, 6), (10, 15), (20, 30)] and set2=[(2, 5), (7, 13)].

Answer 1

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] > interval2[1]:
                interval2 = next(iter2)
            while interval2[0] > 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,...

Answer 2

The really low hanging fruit here is improving getIntersection Rather than special casing everything, you can simply say that the intersection is the distance between the max of the mins, and the min of the maxes (if the end is greater than the start). While we're at it, we might as well clean up some of the naming issues.

def getIntersection(interval_1, interval_2):
    start = max(interval_1[0], interval_2[0])
    end = min(interval_1[1], interval_2[1])
    if start < end:
        return (start, end)
    return None

This is simpler, cleaner, and faster to boot.

The next thing we can do to speed things up from here is to take note of two facts that occur because the intervals are disjoint.

1. If intervals1[i] intersects with intervals2[j], intervals1[i+1] does not intersect with intervals2[j].
2. If intervals1[i] does not intersect with intervals2[j], it does not intersect with intervals2[j+1].

Your original returnInersection code is O(n^2) because it searches the cross product of the two lists. Each of the above rules limits almost half of the space, and if you use both, you only check for O(n) intersections (basically the diagonal) This code does that.

def returnInersection(intervals1, intervals2):
    start = 0
    for interval1 in intervals1:
        found_yet = False
        for j in range(start, len(intervals2)):
            intersection = getIntersection(interval1, intervals2[j])
            if intersection:
                print(intersection)
                found_yet = True
                start += 1
            elif found_yet:
                break

I'm sure there are still ways to speed this up, but it is at least algorithmically optimal.