Intervals

Intervals become simple once you decide the ordering. Most tasks reduce to sorting and then either merging overlaps, picking endpoints greedily, or sweeping two lists with pointers.

Pattern A: Merge overlaps after sorting

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

Invariant: cur is the merged union of all processed intervals so far.

Skeleton:

sort by start
cur = first
for each interval:
    if interval.start <= cur.end:
        cur.end = max(cur.end, interval.end)
    else:
        append cur
        cur = 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:

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:

sort by end
count = 1
end = first.end
for each interval:
    if interval.start > end:
        count++
        end = interval.end
    else:
        // overlap, keep current end

Problems:

• minimum-number-of-arrows-to-burst-balloons.
• non-overlapping-intervals (keep max non-overlapping, removals = n - count).

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.