Interval List Intersection

Merge Intervals

Problem

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)