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.
- If
intervals1[i]
intersects with intervals2[j]
, intervals1[i+1]
does not intersect with intervals2[j]
.
- 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.