Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumintervals

Interval List Intersections

Problem (restated)

Two lists of closed intervals, each list pairwise disjoint and sorted. Return the intersection intervals of the two lists.

Intuition

Two pointers. Intersection of A[i] and B[j] is [max(starts), min(ends)] if nonempty. Advance the interval that ends first.

Approaches

Two-pointer merge of sorted lists

Unverified

Time O(m + n)Space O(1) extra

Idea. Sorted + disjoint guarantees linear scan without missing overlaps.

Walkthrough. [[0,2],[5,10],[13,23],[24,25]] ∩ [[1,5],[8,12],[15,24],[25,26]] → [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]].

Trade-offs. Binary search per interval is worse when both lists are long.

Solution

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

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

Template connection

Interval two-pointer sweep.

Reflection

The overlap is [max(starts), min(ends)], and only when that start is at most that end. Advance the list that finished.
One empty list means no intersection. Is a touch, the single point [x, x], included?
Both lists arrive sorted. Sorting them yourself would change the cost.