Intervals

Reader guide and study workflow · Complete course map

Draw the ranges [1,4], [2,3], and [6,8]. To represent their union exactly, the first two can become [1,4], but the gap from 4 to 6 must survive. What summary would let you decide whether the next interval extends the current component?

Let the requested output choose the ordering

A simple model compares every pair of intervals and joins connected overlap components. It makes the target clear, but checking all pairs is quadratic. Sorting by start changes what a gap proves: once the next start lies beyond the current end, no later start can bridge backward across that gap.

Track one active start and end. For [1,4] followed by nested [2,3], the end remains 4. For a later start 6, emit [1,4] and begin [6,8]. The state summarizes one component, not a single giant range covering every processed interval. This derives both the max-end update and the moment when output becomes final.

Now ask for the largest compatible schedule instead of the union. Starting with a long early interval such as [0,10] can block [1,2], [3,4], and [5,6]; ordering by earliest finish has a better exchange argument. Ask for arrows instead, and an endpoint becomes a covering point rather than a kept interval.

Before writing a comparison, settle equality: [1,2] and [2,3] merge as closed sets, share one arrow at 2, and are compatible in this pack's scheduling exercise. The workshop derives these different decisions from their outputs.

Prerequisites and readiness

Know sort comparators, closed versus endpoint-compatible intervals, and an exchange argument. Before coding, write the exact inequality for touching endpoints in the task at hand.

Reasoning workshop: equality is part of the problem

One drawing, three different questions

Draw [1,2] and [2,3]. For closed-interval union they merge into [1,3]. For balloon arrows, one arrow at 2 hits both. For the non-overlapping scheduling task, both may be retained because a next start equal to the previous end is compatible. Memorizing one “overlap test” and reusing it across all three changes at least one contract.

A point interval [2,2] is allowed by the published bounds. It is a real balloon and a real closed-set intersection. Equal-end scheduling ties need start order: process [1,2] before [2,2] so both can be kept. Sorting only by end with an arbitrary tie order can lose one. In the scheduling exercise it follows the stated start>=previousEnd rule. State the convention before debating whether zero-duration intervals are “really overlapping”; the code must implement this pack's rule, not an unstated real-world calendar policy.

Why sorting by start enables merging

After sorting, maintain the union of the current overlapping component, not the union of every interval seen. In [[1,5],[2,3],[8,9]], the nested [2,3] cannot reduce the active end from 5 to 3. When start 8 exceeds end 5, sortedness proves that no later interval will bridge the gap, so [1,5] is final. Remember to emit the final active interval even when the loop never encounters another gap.

Insertion receives this sorted, disjoint structure as a precondition. Appending the before-region, widening one overlapping component, then appending the after-region avoids a redundant sort. Inserting [2,8] into [[1,2],[4,5],[8,10]] bridges all three and produces [1,10].

Two exchange arguments, not one slogan

For interval scheduling, compare the greedy earliest-finishing interval with the first interval in an optimal schedule. Replacing the latter with the greedy choice leaves at least as much room for every subsequent interval. Repeat this exchange to justify maximizing the number retained. Choosing the earliest start instead can lock in one long interval and block several short ones.

For arrows, the earliest-ending balloon requires some arrow at or before its end e. Move that arrow right to e. Every remaining balloon previously hit by it begins no later than the old arrow and ends no earlier than e, so none of that coverage is lost. This proves that an optimal solution can choose e. It is a coverage exchange, not the same scheduling exchange with a renamed counter.

Discard the interval that finishes first

For intersections, compute lo=max(starts) and hi=min(ends) and emit when lo<=hi. If one interval ends earlier, later intervals from the opposite internally disjoint list cannot intersect it. This justifies advancing its pointer. On first list [[1,2],[5,7]] and second list [[2,5]], the outputs are the point intersections [2,2] and [5,5].

Ownership and testing

Merge, removal scheduling, and arrows sort the outer input slice in place. Insertion and intersection do not need to mutate their inputs. Insertion may return some existing row slices unchanged, so “does not mutate during the call” is weaker than “returns a deep copy.” For correctness oracles, use direct pairwise intersections, exhaustive compatible subsets for scheduling, and exhaustive endpoint covers for small balloon sets. A second implementation of the same greedy loop would be less likely to catch a wrong inequality.

Pattern reference

Use these summaries after deriving the state and the reason each update is safe. The patterns name decisions already justified above.

Pattern A: Merge overlaps after sorting

Use when: you must union intervals or insert into a sorted list.

Invariant: cur is the union of the current overlapping component. Earlier disjoint components are already in output; cur does not cover gaps between them.

Skeleton:

if intervals is empty: return []
sort by start
cur = copy of first
for each interval after the first:
    if interval.start <= cur.end:
        cur.end = max(cur.end, interval.end)
    else:
        append cur
        cur = copy of interval
append cur

Problems:

• merge-intervals.
• insert-interval.

---

Pattern B: Compress consecutive runs

Use when: inputs are sorted numbers and you need [start,end] ranges.

Invariant: start begins a run, and you extend it while the next number is consecutive.

Skeleton:

if nums is empty: return []
start = nums[0]
prev = nums[0]
for x in nums[1:]:
    if x == prev + 1:
        prev = x
    else:
        emit [start, prev]
        start = x
        prev = x
emit [start, prev]

Problems:

• summary-ranges.

---

Pattern C: Greedy by end time

Use when: you want the minimum number of points/arrows or removals.

Invariant: picking the earliest end leaves the most room for future intervals.

Skeleton:

if intervals is empty: return 0
sort by (end, start)
count = 1
end = first.end
for each interval after the first:
    if interval.start > end:
        count++
        end = interval.end
    else:
        // overlap, keep current end

Problems:

• minimum-number-of-arrows-to-burst-balloons: the shown strict start > end branch starts a new arrow.
• non-overlapping-intervals: use start >= end to keep another compatible interval; removals = n - kept. These inequalities are deliberately different.

---

Pattern D: Two-pointer intersection

Use when: you need intersections of two sorted interval lists.

Invariant: pointers i and j track the next candidate intervals in each list.

Skeleton:

while i < A and j < B:
    lo = max(A[i].start, B[j].start)
    hi = min(A[i].end, B[j].end)
    if lo <= hi: add [lo, hi]
    if A[i].end < B[j].end: i++ else: j++

Problems:

• interval-list-intersections.

---

When to use Intervals (checklist)

• Data are start/end pairs or can be treated as such.
• You can sort without violating requirements.
• Overlap logic or endpoint choice is the core difficulty.

Common failures (checklist)

• Confusing inclusive vs exclusive endpoints.
• Forgetting to append the last merged interval.
• Sorting by start when greedy-by-end is required.
• Using >= vs > incorrectly for overlap checks.

Problem mapping

• summary-ranges: compress consecutive numbers into intervals.
• merge-intervals: union after sort.
• insert-interval: merge into sorted list.
• non-overlapping-intervals: greedy by end.
• minimum-number-of-arrows-to-burst-balloons: greedy by end.
• interval-list-intersections: two-pointer sweep.

Reconstruction lab and answer key

Close the worked examples before attempting these new cases. Rebuild the state and justify the update, then compare with the model answer.

Summary Ranges

For sorted unique [4,5,9,10], when is each range emitted? What fails if emission happens only on gaps?

Model answer

The gap before 9 emits "4->5". The end-of-input flush emits "9->10". A gap-only implementation loses the final run, including the whole answer when there is just one run.

Merge Intervals

Trace [[6,8],[1,7],[2,3]] after sorting. Why can current.end never be assigned the next end unconditionally?

Model answer

Sorted order is [1,7],[2,3],[6,8]. The nested interval leaves end at 7; [6,8] then extends it to 8, yielding [1,8]. Assigning end=3 at the nested interval would create a false gap before 6.

Insert Interval

Insert [3,4] into [[0,1],[6,7]]. Which rows can be appended unchanged, and does that mean the returned result is a deep copy?

Model answer

Append [0,1], then new [3,4], then [6,7]. The reference may share the two unchanged input rows with the result. Not mutating inputs during the call does not promise independent storage after the call.

Non-overlapping Intervals

Both [4,4] and [1,4] finish at 4. Which tie order permits keeping both under this task’s rule, and what happens with the opposite order?

Model answer

Process [1,4] before [4,4]: the second start equals the saved end, so both fit. Processing the point first sets end=4 and incorrectly rejects start 1. Break end ties by increasing start to preserve the zero-length case.

Minimum Number of Arrows to Burst Balloons

For [[0,4],[2,6],[5,8]], derive the first arrow position from the exchange argument, then explain whether the third balloon is already hit.

Model answer

The earliest end is 4. An arrow hitting [0,4] can move right to 4 without losing any remaining balloon it previously hit, since all ends are at least 4. This hits [2,6] too, but [5,8] starts after 4 and needs a second arrow.

Interval List Intersections

When A[i] and B[j] end at the same coordinate, is it safe to advance both pointers? State the precondition that makes the answer true.

Model answer

Yes, when each list is sorted and internally disjoint as closed intervals. Later intervals in either list start strictly after that shared end, so neither current interval can contribute another intersection. Advancing only one is also correct, with one harmless extra comparison.

Problems in this module

• Summary Ranges
• Merge Intervals
• Insert Interval
• Non-overlapping Intervals
• Minimum Number of Arrows to Burst Balloons
• Interval List Intersections

Interactive checkpoint

Open the Intervals quiz. The questions use exact, objectively gradeable answers. Work the reasoning drills above before opening their model answers.

Earlier-edition deep links

These anchors preserve links to headings from the original files. They do not reinstate superseded explanations.

Learner experience: how to make this topic stick

The moves to recognize

How to practice without turning it into grind

Debugging instincts to build

A small way to make it memorable