- intersection == overlap is the max of starts and min of ends
- check we're comparing a lower start to a higher or equal end (a valid interval) before appending to result
- increment move past the interval with lower end because it could only have intersected with the other interval with higher end i.e. we already used that intersection for this pair
Input: firstList = [0,2],[5,10],[13,23],[24,25](/ALawliet/algorithms/wiki/0,2],[5,10],[13,23],[24,25), secondList = [1,5],[8,12],[15,24],[25,26](/ALawliet/algorithms/wiki/1,5],[8,12],[15,24],[25,26)
Output: [1,2],[5,5],[8,10],[15,23],[24,24],[25,25](/ALawliet/algorithms/wiki/1,2],[5,5],[8,10],[15,23],[24,24],[25,25)
class Solution:
def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
res = []
a = b = 0
while a < len(A) and b < len(B):
A_start, A_end = A[a][0], A[a][1]
B_start, B_end = B[b][0], B[b][1]
lo = max(A_start, B_start) # bigger start
hi = min(A_end, B_end) # smaller end
if lo <= hi: # is an intersection
res.append( [lo, hi] )
if A_end < B_end: # increment smaller end
a += 1
else:
b += 1
return res