Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Enquire Book a call

Coding · Intervals

Understanding the problem

Lesson · 8 min read · Intervals

Why checking every pair of ranges is the slow way, how sorting makes overlaps sit next to each other, and how to tell which end to sort by.

Every pair is the slow way

A calendar holds bookings, each a start and an end, and you want to know which of them overlap. Two ranges [a, b] and [c, d] overlap exactly when a < d and c < b, so the direct answer checks every pair: about n²/2 checks. For a day of 2,000 bookings that is two million; for a year of an exchange's trading sessions, far more.

Most of those checks compare ranges that are nowhere near each other. A booking at 9 a.m. and one at 4 p.m. cannot overlap, and the pairwise loop has no way of knowing that without looking.

Sort, and overlaps become neighbours

Sort the ranges by start time. Now any range that overlaps the current block of merged ranges comes straight after it: a later range starts later, so if it doesn't start before the block ends, nothing after it will either. One pass is enough. Each range either extends the current block or, if it starts after the block ends, closes it and opens a new one.

Note the max when extending: a range that sits entirely inside the block, like 3–4 inside 1–5, must not shorten it.

Six ranges merged into blocks after a sort by start. Each one is looked at once.

  1. Step 1 / 6
    ranges, sorted by start
    1–302–513–426–8310–12411–135
    blocks
    1–30

    Sorted by start: 1–3, 2–5, 3–4, 6–8, 10–12, 11–13. The first range opens a block, 1–3.

  2. Step 2 / 6
    ranges, sorted by start
    1–302–513–426–8310–12411–135
    blocks
    1–50
    blocks1

    2–5 starts at or before 3, inside the current block. The block now runs to 5.

  3. Step 3 / 6
    ranges, sorted by start
    1–302–513–426–8310–12411–135
    blocks
    1–50
    blocks1

    3–4 starts at or before 5, inside the current block. It ends inside the block, so nothing changes.

  4. Step 4 / 6
    ranges, sorted by start
    1–302–513–426–8310–12411–135
    blocks
    1–506–81
    blocks2

    6–8 starts after 5: there is a gap, so the block before it is final. Start a new block.

  5. Step 5 / 6
    ranges, sorted by start
    1–302–513–426–8310–12411–135
    blocks
    1–506–8110–122
    blocks3

    10–12 starts after 8: there is a gap, so the block before it is final. Start a new block.

  6. Step 6 / 6
    ranges, sorted by start
    1–302–513–426–8310–12411–135
    blocks
    1–506–8110–132
    blocks3

    11–13 starts at or before 12, inside the current block. The block now runs to 13.

Which end to sort by

The sort depends on the question. To merge or measure ranges, sort by start, as above. To choose as many non-overlapping ranges as possible, sort by end, and keep each range that starts after the last one you kept. The range that ends first leaves the most room for the rest, and swapping it into any best answer never makes that answer worse.

Sorting by start fails at choosing. With ranges 1–10, 2–3 and 4–5:

RuleKeepsHow many
Earliest start first1–10 (it blocks the other two)1
Earliest end first2–3, then 4–52

Counting what is open: the sweep line

How many meeting rooms does a day of meetings need? Exactly the most meetings running at one moment. That count only changes when a meeting starts or ends, so turn every meeting into two events, +1 at its start and −1 at its end, sort the events by time, and keep a running count.

The one subtle rule is ties. With meetings that free their room at time t for one starting at t, the end must be counted before the start, or back-to-back meetings look like a clash.

Three tools cover almost every interval question: sort by start to merge, sort by end to choose, sweep the events to count. When the ranges carry values and you must pick the most valuable set, keep the sort by end and let dynamic programming make the choice.

Four meetings as start and end events. The running count is the number of rooms in use.

  1. Step 1 / 9
    events
    1+02+13−23+34−44+55−66−7
    open0most0

    Every range becomes two events: + at its start, − at its end. Sorted by time, with ends first when times are equal: 1+ 2+ 3− 3+ 4− 4+ 5− 6−.

  2. Step 2 / 9
    events
    1+02+13−23+34−44+55−66−7
    open1most1

    A range starts at 1. Open now: 1. That equals the most so far.

  3. Step 3 / 9
    events
    1+02+13−23+34−44+55−66−7
    open2most2

    A range starts at 2. Open now: 2. That equals the most so far.

  4. Step 4 / 9
    events
    1+02+13−23+34−44+55−66−7
    open1most2

    A range ends at 3. Open now: 1.

  5. Step 5 / 9
    events
    1+02+13−23+34−44+55−66−7
    open2most2

    A range starts at 3. Open now: 2. That equals the most so far.

  6. Step 6 / 9
    events
    1+02+13−23+34−44+55−66−7
    open1most2

    A range ends at 4. Open now: 1.

  7. Step 7 / 9
    events
    1+02+13−23+34−44+55−66−7
    open2most2

    A range starts at 4. Open now: 2. That equals the most so far.

  8. Step 8 / 9
    events
    1+02+13−23+34−44+55−66−7
    open1most2

    A range ends at 5. Open now: 1.

  9. Step 9 / 9
    events
    1+02+13−23+34−44+55−66−7
    open0most2

    A range ends at 6. Open now: 0. The most ranges open at once is 2.