Interval List Intersections With Two Sorted Pointers

This one is a Medium-rated classic reported from Meta, Google, Airbnb interviews: "Interval List Intersections". Like every post in this series, the goal is not memorizing the answer — it is recognizing the Merge Intervals pattern on sight. Part 6 of 11 in the Merge Intervals arc.

The Problem

Given two lists of closed, disjoint, sorted intervals, return their intersections. Two calendars, find the times busy in both — Meta has asked exactly this phrasing for years. The mechanics: every intersection is max-of-starts to min-of-ends, when that range is non-empty.

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]]

Recognizing the Merge Intervals Pattern

Interval problems — scheduling, calendars, resource booking — almost all reduce to one move: sort by start (or end), then sweep once while comparing each interval against a running boundary. Overlap exists when the next start is at most the current end. Sort plus linear sweep, O(n log n), is the backbone of the entire family.

Two sorted sequences consumed together is merge-style two pointers layered onto interval arithmetic. The only decision each step is which pointer advances: the interval with the smaller end is exhausted — nothing later in the other list can intersect it.

The Approach

Hold indices i and j. Compute lo = max(starts), hi = min(ends); if lo is at most hi, emit [lo, hi]. Then advance whichever interval ends first — advancing the other would skip potential intersections with its remaining span.

The advance rule is the interview: articulate why smaller-end-moves in one sentence, and handle the equal-ends case (either advances; both is also fine as two steps).

Python Solution

def interval_intersection(
    a: list[list[int]], b: list[list[int]]
) -> list[list[int]]:
    """Intersections of two sorted disjoint closed-interval lists."""
    result: list[list[int]] = []
    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])
        if a[i][1] < b[j][1]:      # a's interval is exhausted
            i += 1
        else:
            j += 1
    return result

Complexity

• Time: O(n + m) — each step advances one of the two pointers
• Space: O(n + m) — output can contain up to n + m − 1 intersections

Interview Tips and Follow-Ups

• Closed intervals make [5, 5] a valid single-point intersection — half-open conventions would drop it. Ask which one the interviewer means.
• Extension: intersect k calendars — pairwise reduction works, or a k-way sweep; sketch the trade-off before being asked.
• The advance rule's mirror is the merge step of merge sort — connecting interval problems to merge mechanics is a pattern-level insight worth voicing.

That wraps part 6 of the Merge Intervals arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.