Interval List Intersections

Given two lists of closed intervals, each list is sorted by start and non-overlapping within itself. Return their intersections.

Why this is worth learning

Once the interval with the earlier end has been compared against its current counterpart, it cannot intersect a later interval from the other disjoint sorted list.

Before coding: one-minute experiment

What is the intersection of [[1,2],[5,7]] and [[2,5]]?

Function signature

func IntervalIntersection(first [][]int, second [][]int) [][]int

Inputs / outputs

• first, second: lists of non-overlapping intervals sorted by start.
• Return: list of intersections, also sorted.

Example

first = [[0,2],[5,10],[13,23],[24,25]]
second = [[1,5],[8,12],[15,24],[25,26]]
Output = [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Constraints

• 0 <= len(first), len(second) <= 100_000
• -1_000_000_000 <= start <= end <= 1_000_000_000

Core idea (near-solution)

Use two pointers. For the current intervals, the intersection (if any) is:

• start = max(a.start, b.start)
• end = min(a.end, b.end)

If start <= end, record it. Then advance the pointer of the interval that ends first.

Invariant: all intersections before the current pointers have been recorded.

Algorithm (step-by-step)

1. Initialize i = 0, j = 0.
2. While i < len(first) and j < len(second):
   • Compute overlap.
   • If overlap exists, append it.
   • Advance the pointer whose interval ends first.
3. Return the result.

Correctness sketch

The intersection of two closed intervals is [max(starts),min(ends)] when that lower bound is at most the upper bound. Emit exactly that range. Suppose the first interval ends earlier. Every later interval in the second list starts after the current second interval ends, which is no earlier than the first interval's end; therefore the first interval has no unexamined intersections and its pointer can advance. The symmetric case advances the second pointer. This discard argument preserves all possible future intersections. Each iteration advances at least one pointer, visits pairs in order, and emits only real overlaps, giving the complete ordered result.

Trace (hand walkthrough)

Example input:
first = [[0,2],[5,10],[13,23],[24,25]]
second = [[1,5],[8,12],[15,24],[25,26]]
Output = [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Walk:
- [0,2] ∩ [1,5] -> [1,2], advance first
- [5,10] ∩ [1,5] -> [5,5], advance second
- [5,10] ∩ [8,12] -> [8,10], advance first
- [13,23] ∩ [15,24] -> [15,23], advance first
- [24,25] ∩ [15,24] -> [24,24], advance second
- [24,25] ∩ [25,26] -> [25,25]

Pitfalls to avoid

• Forgetting to advance the correct pointer.
• Missing intersections when one interval fully contains another.

Debugging lens

Use empty lists, one long interval against several short ones, and equal ending coordinates. Test each input is preserved; neither list needs sorting or mutation.

Complexity

• Time: O(n + m)
• Extra space: O(1) beyond output.

Implementation notes (Go)

• Use two pointers; add overlap when lo <= hi.
• Advance the pointer with the smaller end.

Contract precision

Each input list is internally disjoint as closed intervals, so successive intervals do not share an endpoint within one list. Point intersections between different lists are valid. Both inputs remain unchanged.

Reconstruction checkpoint

What is the intersection of [[1,2],[5,7]] and [[2,5]]?

Return to Intervals · Module quiz