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, interval_2)
end = min(interval_1, interval_2)
if start < end:
return (start, end)
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.
intervals1[i] intersects with
intervals1[i+1] does not intersect with
intervals1[i] does not intersect with
intervals2[j], it does not intersect with
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])
found_yet = True
start += 1
I'm sure there are still ways to speed this up, but it is at least algorithmically optimal.