Intervals

Problems about ranges such as meetings, bookings and time slots: merging them, finding overlaps and counting how many run at once. Sorting, then one pass, solves most of them.

Overview

The idea

An interval is a pair [start, end]. Checking every pair of intervals for overlap costs O(n²). Almost every interval problem is solved faster by putting the intervals in order first. After sorting, intervals that can overlap sit next to each other, so one pass over the list is enough. The sort costs O(n log n) and dominates.

Combine overlapping ranges — start — extend the last range or start a new one — Merge Intervals, Insert Interval
Can one person attend all? — start — check each pair of neighbors — Meeting Rooms
How many at the same time? — start (or events by time) — min-heap of end times, or a sweep line — Meeting Rooms II, Car Pooling
Keep the most non-overlapping — end — greedy: take the one that ends first — Non-overlapping Intervals, Minimum Number of Arrows
Overlap of two sorted lists — already sorted — one pointer per list — Interval List Intersections

When do two intervals overlap?

Two intervals [a, b] and [c, d] overlap when each one starts before the other ends. It is easier to remember the opposite: they do not overlap when one ends before the other starts.

The one question to settle is whether touching counts. Meetings [1, 2] and [2, 3] can share a room, because the first ends as the second starts. Closed ranges of integers such as [1, 2] and [2, 3] do share the point 2.

Half-open, like meetings — start included, end excluded — a 10) — 3-10

The result is [[1, 2], [3, 10], [12, 16]].

How many rooms: a min-heap of end times

First sort the meetings by start, and keep a min-heap (a structure that always gives back its smallest item) of the end times of meetings that hold a room. For each meeting, if the earliest end is at or before its start, that room is free: pop it. Then push the new end. The heap never shrinks by more than one per meeting, and its size at the end is the number of rooms needed.

0-30 — none — no — 30 — 1
5-10 — 30 — no — 10, 30 — 2
10-25 — 10 — yes, reuse — 25, 30 — 2
15-20 — 25 — no — 20, 25, 30 — 3

Sweep line: count starts and ends

A sweep line turns each interval into two events: +1 at its start and -1 at its end. Sort the events by time and keep a running total. The largest total is the most intervals active at once.

0 — start — 1 — 1
5 — start — 2 — 2
10 — end — 1 — 2
10 — start — 2 — 2
15 — start — 3 — 3
20 — end — 2 — 3
25 — end — 1 — 3
30 — end — 0 — 3

At time 10 the end is processed before the start. With half-open meetings that is correct: a room freed at 10 can be used at 10. Sorting the pairs (time, -1) and (time, +1) as tuples puts -1 first on its own.

When the times are small integers, a difference array does the same job without sorting: add at the start index, subtract just after the end, then take a running sum. Three bookings on flights 1 to 5 (10 seats on 1 to 2, 20 on 2 to 3, 25 on 2 to 5):

Change — +10 — +45 — -10 — -20 — 0
Running sum — 10 — 55 — 45 — 25 — 25

Keep the most intervals: sort by end

To keep as many non-overlapping intervals as possible, sort by end and take each interval that starts at or after the end of the last one taken. The interval that ends first leaves the most room for the rest. The Greedy topic proves this and shows why sorting by start or by length fails.

Non-overlapping Intervals (fewest to remove) — n minus the number kept
Minimum Number of Arrows to Burst Balloons — the number kept, with touching counted as overlap

Two sorted lists: one pointer each

For Interval List Intersections, look at the current interval of each list. Their overlap, if any, is from the larger start to the smaller end. Then move past whichever interval ends first, because it cannot overlap anything later in the other list.

0-2 — 1-5 — 1-2 — A (ends at 2)
5-10 — 1-5 — 5-5 — B
5-10 — 8-12 — 8-10 — A
13-23 — 8-12 — none — B
13-23 — 15-24 — 15-23 — A
24-25 — 15-24 — 24-24 — B
24-25 — 25-26 — 25-25 — A, list done

Spotting an interval problem

Ranges, meetings, bookings, time slots — sort by start first
'Merge', 'combine', 'union' — merge pass
'Minimum rooms', 'maximum at once', 'capacity' — min-heap of ends or sweep line
'Remove the fewest', 'attend the most' — sort by end, greedy
Many range updates, then read all values — difference array
Two sorted lists of ranges — one pointer per list

> [!TIP] > Draw the intervals on a number line before coding. It shows which sort key to use and whether touching ranges matter.

What you will be able to do

Write the overlap test and say whether touching counts.
Merge and insert intervals, including one interval inside another.
Count the rooms needed with a min-heap or a sweep line, and explain the tie at equal times.
Choose between sorting by start and sorting by end.
Use a difference array for many range updates.

When to use it

Merging overlapping ranges
Meeting room and calendar scheduling
Counting the most intervals active at once (capacity, rooms, car pooling)
Keeping the most non-overlapping intervals, or removing the fewest
Finding free time: the gaps between merged intervals
Many range updates followed by one read of all values (difference array)

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio