What should the union preserve?

Intervals [1,4], [2,3], [6,8].

Which gap must remain? Why can a nested interval never reduce the active end?

1 / 9

Ordering changes the proof

All-pairs overlap components are a correct starting model.

Sorting by start makes a gap final: later starts cannot bridge backward.

Does the same first-choice rule maximize a schedule?

2 / 9

Summary Ranges — predict before coding

A range ends exactly at a gap in the sorted unique input. Maximal consecutive runs are both sufficient and necessary for the smallest exact cover.

Decision: How should [-2,-1,1,3,4] be represented?

Presenter notes

Model answer: ["-2->-1","1","3->4"]. The absent 0 and 2 force separate ranges, and the singleton 1 has no arrow.

Correctness argument: Keep the first and last values of the current consecutive run. If the next value equals previous+1, extending the run preserves exact coverage without gaps. Otherwise the gap prevents any exact integer range from covering both the current run and the next value, so emitting the current run is forced. Restarting at the new value preserves the invariant that prior output covers precisely the finished prefix. After the scan, emit the final run. Every emitted range is maximal, and every gap forces a boundary, so no representation with fewer exact ranges is possible.

Debugging prompt: Test a final singleton, all consecutive values, negative transitions, and empty input. Forgetting the final flush loses the last run.

3 / 9

Merge Intervals — predict before coding

Sorting by start lets a single active interval summarize the union of everything overlapping the current component. Closed intervals that touch at an endpoint merge.

Decision: What does merging [[1,3],[3,5],[8,8]] produce?

Presenter notes

Model answer: [[1,5],[8,8]]. Endpoint 3 belongs to both closed intervals, so the first two merge.

Correctness argument: After sorting, all completed output intervals lie strictly before the active merged interval, and the active interval is the union of its overlapping component seen so far. If the next start is at most the active end, the intervals overlap or touch; replacing the end by their maximum preserves exactly their union. If the next start exceeds the active end, no later interval can bridge this gap because all later starts are at least as large. The active interval is therefore final and may be emitted. Induction followed by a final flush produces precisely the connected components of the union, in sorted non-overlapping order.

Debugging prompt: Use nested intervals, equal starts, touching endpoints, and an interval entirely containing all others. Update end with max, not by blindly assigning the next end.

4 / 9

Insert Interval — predict before coding

The input already supplies the sorted disjoint structure that Merge Intervals would otherwise have to build. Exploit it with before, overlapping, and after phases.

Decision: Insert [2,8] into [[1,2],[4,5],[8,10]]. What remains?

Presenter notes

Model answer: [[1,10]]. Touching at 2 and 8 counts as overlap for closed intervals, and the insertion bridges all three intervals.

Correctness argument: Intervals ending before the new start are disjoint and can be copied directly to output. Thereafter, while a next start is at most the growing merged end, it overlaps the new component; widening start and end to the minimum and maximum preserves that component's exact union. Once a next start exceeds the merged end, sortedness proves every remaining interval is disjoint and later, so the merged interval is final. Appending the untouched suffix completes the union in order. The phases cover every old interval exactly once and insert exactly one merged component, including when the original list is empty.

Debugging prompt: Test an insertion before everything, after everything, wholly inside one interval, and spanning every interval. Do not sort again or mutate newInterval unless the contract explicitly requires it.

5 / 9

Non-overlapping Intervals — predict before coding

Maximizing the number retained is equivalent to minimizing removals. Keep the earliest-finishing compatible interval because it leaves the largest future opportunity.

Decision: How many intervals must be removed from [[1,2],[2,3],[1,3]]?

Presenter notes

Model answer: One. Keep [1,2] and [2,3]; sharing endpoint 2 is allowed for this scheduling problem.

Correctness argument: Among intervals available after the last chosen end, take one with the earliest end. Any optimal remaining schedule has a first interval whose end is no earlier. Replacing that first interval with the greedy choice cannot block any later interval, because the replacement frees the timeline at least as early. Thus some optimal schedule starts with the greedy choice. Repeating the exchange argument on the remaining compatible intervals proves the maximum retained count. Subtracting this count from n gives minimum removals. Compatibility here permits a next start equal to the previous end, unlike closed-interval merging.

Debugging prompt: Include equal finish times, nested intervals, touching intervals, and allowed zero-length intervals. A start-sorted greedy choice can retain a long interval that blocks several short ones.

6 / 9

Minimum Number of Arrows to Burst Balloons — predict before coding

An arrow position must hit the earliest-ending remaining balloon. Move that mandatory arrow as far right as possible, to its end, without losing any useful earlier coverage.

Decision: How many arrows are needed for [[1,2],[2,3]], and where can the arrow be placed?

Presenter notes

Model answer: One arrow at 2 hits both balloons, because balloon intervals include both endpoints.

Correctness argument: Let e be the smallest end among unburst balloons. Every solution needs some arrow x within that earliest-ending balloon, hence x<=e. Any remaining balloon hit by x has start<=x<=e and end>=e by minimality, so it is also hit by an arrow moved to e. This exchange loses no coverage and establishes an optimal solution whose next arrow is at e. Remove all balloons containing e and repeat. In end-sorted order, a balloon needs a new arrow exactly when its start is greater than the current arrow position. Counting these necessary greedy choices yields the minimum.

Debugging prompt: Do not use >= when deciding to start another arrow; endpoint contact is sufficient. Test duplicate balloons, point balloons, nested ranges, and empty input.

7 / 9

Interval List Intersections — predict before coding

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.

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

Presenter notes

Model answer: [[2,2],[5,5]]. Point intersections at closed endpoints are valid and must not be discarded.

Correctness argument: 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.

Debugging prompt: 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.

8 / 9

Reconstruct and transfer

Reconstruct the two different exchange arguments.

Explain why the earlier-ending interval can be discarded in intersection.

Identify which routines mutate input order.

9 / 9