Interval List Intersections

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

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

• Invariant: all intersections before the current pointers have been recorded.
• Sorting establishes a consistent processing order.
• Merge/greedy steps maintain a correct partial solution.
• After processing all intervals, the result is optimal and complete.

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.

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.