Interval List Intersections

Problem Statement

Given two lists of closed, sorted, disjoint intervals, return their intersection — every range that appears in both lists.

Input

Two arrays of intervals, each already sorted and pairwise disjoint.

firstList  = [[0,2],[5,10],[13,23],[24,25]]
secondList = [[1,5],[8,12],[15,24],[25,26]]

Output

A sorted list of the intersecting intervals.

[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Constraints

• 0 ≤ firstList.length, secondList.length ≤ 1000
• firstList.length + secondList.length ≥ 1
• 0 ≤ startᵢ < endᵢ ≤ 10⁹
• Each input list is already sorted and contains disjoint intervals.

Intuition

Two pointers — one per list. At each step compute the candidate intersection using [max(starts), min(ends)]. If lo ≤ hi, add it. Then advance the pointer whose interval ends first — it can’t intersect anything else from the other list.

  A:  [──────]      ← ends earliest, can't match more B's
  B:     [──────────]
         ▓▓▓         ← intersection = [max(starts), min(ends)]
 
  After recording, A moves forward; B still has room to match new A's.

Solution

def intervalIntersection(A: list, B: list) -> list:
    result = []
    i = j = 0
 
    while i < len(A) and j < len(B):
        lo = max(A[i][0], B[j][0])
        hi = min(A[i][1], B[j][1])
 
        if lo <= hi:
            result.append([lo, hi])
 
        # Advance the pointer with the smaller end
        if A[i][1] < B[j][1]:
            i += 1
        else:
            j += 1
 
    return result

function intervalIntersection(A: number[][], B: number[][]): number[][] {
    const result: number[][] = [];
    let i = 0, j = 0;
 
    while (i < A.length && j < B.length) {
        const lo = Math.max(A[i][0], B[j][0]);
        const hi = Math.min(A[i][1], B[j][1]);
 
        if (lo <= hi) result.push([lo, hi]);
 
        if (A[i][1] < B[j][1]) i++;
        else j++;
    }
 
    return result;
}

Complexity

Edge Case Thinking