Interval list intersections

986.Interval List Intersections

Array

Two Pointers

Interval

Problem Statement:

Given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Return the intersection of these two interval lists.

Example:

Input:

firstList = [[0,2],[5,10]], secondList = [[1,5],[8,12]]

→

Output:

[[1,2],[5,5],[8,10]]

Java Solution:

public int[][] intervalIntersection(int[][] A, int[][] B) {
    int i = 0, j = 0;  // Two pointers for each list
    
    List<int[]> intervals = new ArrayList<>();
    
    while (i < A.length && j < B.length) {
        // Calculate and add intersect
        if (intersect(A[i], B[j]) != null) 
            intervals.add(intersect(A[i], B[j]));
        
        // Increment the one that ends first
        if (A[i][1] < B[j][1]) i++; 
        else j++;  
    }
    
    return intervals.toArray(new int[0][0]);      
}

public int[] intersect(int[] a, int[] b) {
    int[] intersect = new int[] { 
        Math.max(a[0], b[0]),  // Start of intersection
        Math.min(a[1], b[1])   // End of intersection
    };
    return intersect[0] > intersect[1] ? null : intersect;
}

Python Solution:

def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
    result = []
    i = j = 0
    
    while i < len(A) and j < len(B):
        # Find intersection points
        start = max(A[i][0], B[j][0])
        end = min(A[i][1], B[j][1])
        
        # Add valid intersection
        if start <= end:
            result.append([start, end])
            
        # Move pointer of interval that ends first
        if A[i][1] < B[j][1]:
            i += 1
        else:
            j += 1
            
    return result

C++ Solution:

class Solution {
public:
    vectorint>> intervalIntersection(vectorint>>& A, 
                                            vectorint>>& B) {
        vectorint>> result;
        int i = 0, j = 0;
        
        while(i < A.size() && j < B.size()) {
            int start = max(A[i][0], B[j][0]);
            int end = min(A[i][1], B[j][1]);
            
            if(start <= end) {
                result.push_back({start, end});
            }
            
            if(A[i][1] < B[j][1]) i++;
            else j++;
        }
        
        return result;
    }
};

Complexity:

Time: O(M + N) where M and N are lengths of input arrays | Space: O(M + N) for output array