Given two lists of intervals, find the intersection of these two lists. Each list consists of disjoint intervals sorted on their start time.
For example:
Input: A = [[0,2],[5,10],[13,23],[24,25]],
B = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Thought Process
Solution
class Solution:
def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
i, j = 0, 0
res = []
while i < len(A) and j < len(B):
a_overlap = A[i][0] >= B[j][0] and A[i][0] <= B[j][1]
b_overlap = B[j][0] >= A[i][0] and B[j][0] <= A[i][1]
if(a_overlap or b_overlap):
res.append([max(A[i][0], B[j][0]), min(A[i][1], B[j][1])])
if A[i][1] < B[j][1]:
i+=1
else:
j+=1
return res
#We are comparing the intervals start times since we
#don't know which interval start time is smaller
between the two
#If two intervals intersect, we take the maximum start
#time and minimum end time
#Time: O(N+M)
#Space: O(1)
