Overview

Interval problems describe ranges — meetings, bookings, balloons on a number line — and ask how they overlap. Two intervals [a, b] and [c, d] overlap exactly when a ≤ d and c ≤ b. Once intervals are sorted by start, any overlap must be with the most recently kept interval, so a single linear pass can merge them.

A second family is about counting overlaps at each point in time. The sweep-line technique turns each interval into two events (+1 at the start, −1 at the end), sorts the events and walks through them keeping a running count. The peak count is the number of rooms, platforms or machines needed.

Key concepts

Tick a concept once you can explain it in your own words without notes.

Complexity cheat sheet

OperationCost
Sort intervalsO(n log n)
Merge after sortingO(n)
Sweep line over 2n eventsO(n log n)

Patterns to recognise

Merge

Use it for: Merge intervals, insert interval, summary ranges.

Sort by start; extend the last interval or start a new one.

Greedy by end time

Use it for: Non-overlapping intervals, minimum arrows to burst balloons.

Sort by end; take an interval whenever it starts after the last chosen end.

Two-list intersection

Use it for: Interval list intersections.

Two pointers, one per list; advance the one that ends first.

Code template

Merge overlapping intervals
def merge(intervals):
    intervals.sort(key=lambda iv: iv[0])
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)   # overlap: extend
        else:
            merged.append([start, end])
    return merged

Common mistakes

  • Whether [1, 2] and [2, 3] overlap depends on the problem — read it carefully.
  • When extending, take max(end, current end); a later interval can be fully contained in the previous one.
  • In sweep lines, decide whether an end event at time t is processed before a start event at t.

Quick check

Three questions on Intervals. Get all three right to earn +15 XP.

  1. What is the first step in merging overlapping intervals?

  2. Intervals [a, b] and [c, d] with a <= c overlap when:

  3. To keep the maximum number of non-overlapping intervals, the greedy choice is to always pick the one that:

Challenges

Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.

Stuck on Intervals?Ask Orbi for a hint, a fresh explanation or a review of your code.

Ask the tutor