In a two-pointer scan of two sorted interval lists, why advance the pointer whose interval ends first?

## The setting Two ground stations each keep a list of the windows during which a satellite is visible to them. Each list is sorted by start time and **internally disjoint** — one station's windows never overlap each other. The task is to report every window during which the satellite is visible to *both* stations at once. The brute-force answer is to test every window of one list against every window of the other, which is `O(n * m)`. The two-pointer scan does it in `O(n + m)`, and the whole thing turns on one rule: **advance the pointer whose current interval ends first**. ## The two moving parts **Emitting.** For the two intervals currently under the pointers, the shared window is `[max(A[i].start, B[j].start), min(A[i].end, B[j].end))`. It is non-empty — and therefore worth emitting — exactly when that lower bound is strictly less than that upper bound. That is the pairwise overlap condition restated in terms of the two extrema, and it is the only overlap test the scan needs. **Advancing.** Exactly one pointer moves per step, and it is the one whose interval has the smaller end (ties can go either way). ## Why the smaller end is the right one to retire Say `A[i].end <= B[j].end`. Look at what `A[i]` could still possibly meet: - It has already been compared against `B[j]`. - The next window in `B` begins at or after `B[j].end` — that is what *sorted and internally disjoint* buys you — and `B[j].end >= A[i].end`. So `B[j+1].start >= A[i].end`, which means `A[i]` and `B[j+1]` fail the overlap test, and so does every window after it, since starts only grow. `A[i]` therefore has no remaining business anywhere in `B`, and dropping it discards no intersection. The symmetric argument holds when `B[j]` ends first. Since each step retires exactly one interval and never revisits it, the scan makes at most `n + m` steps. ## The wrong rule, and what it costs The tempting alternative is to advance whichever interval *starts* first. That breaks immediately: an early-starting window may be long and still overlap several windows ahead in the other list. Retiring it after one comparison silently drops those intersections. A related mistake is advancing *both* pointers after emitting a result — the same trap, since the interval that outlasts the other still has intersections waiting. ## The precondition is not decoration The safety argument used both properties of each list: sorted by start **and** internally non-overlapping. If one list may contain windows that overlap each other, `B[j+1].start` is no longer bounded below by `B[j].end`, and `B[j+1]` may well still intersect the `A[i]` you just retired. If the input can be ragged, the honest fix is to normalise each list first — coalesce each list into disjoint windows sorted by start — and then run the scan. Saying that precondition out loud is a large part of what the question is testing. ## Cost and alternatives The scan is `O(n + m)` time and `O(1)` auxiliary space beyond the output. Pouring both lists into one collection and sorting is `O((n + m) log(n + m))` and throws away the ordering the inputs already had; it is the right move only when the inputs genuinely arrive unsorted. When the lists are wildly asymmetric — one holds a handful of windows, the other holds millions — the linear scan is no longer the obvious winner: locating each of the few windows by binary search into the large sorted list costs `O(k log N)`, which beats `O(N)` when `k` is small. That is a real judgment call rather than a trick, and it depends on knowing the shape of the data. ## Boundary details worth stating - Under half-open semantics, emit only when the computed lower bound is **strictly** below the upper bound; two windows that merely touch produce an empty result and should be dropped, not emitted as a zero-length window. - Ties in the end comparison are harmless: advancing either pointer is correct, because when both ends are equal both intervals are simultaneously finished with respect to the other list. - The scan generalises to more than two lists only awkwardly; with three or more, the pairwise fold — intersect two, then intersect the result with the third — keeps the same linear character per step and is far easier to defend than a k-way pointer dance.