How many rooms do the bookings need at once?

Greedy choices and intervals Mid-level Python 3.13+ Kotlin 2.4+ Reviewed 1 Nov 2026 By Best Latest Apps

Predict the output

What does this print?

Python 3.13

bookings = [[0, 30], [5, 10], [10, 20], [15, 25]]
starts = [(s, 1) for s, _ in bookings]
ends = [(e, -1) for _, e in bookings]
events = sorted(starts + ends)
live = peak = 0
for _, d in events:
    live += d
    peak = max(peak, live)
print(peak)

Options342

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 3

Right: at time 15, three bookings run together.

Ends sorting first at time 10 is what stops [5, 10) and [10, 20) from counting together.

Why not the others?

B 4. [5, 10) has ended before [10, 20) starts, so all four never overlap.
C 2. From 15 to 20, [0, 30), [10, 20) and [15, 25) overlap.

30-second answer

Turn each booking into two events: +1 at its start and -1 at its end. Sort the events by time, with ends before starts at the same time (half-open). Sweep through, keeping a running count; the largest count is the answer. O(n log n) time and O(n) space. A min-heap of end times gives the same result.

Practise saying it · 45 s. No recording, just a timer

Explain counting rooms with a sweep.

Say your answer out loud, then check which of these points you covered:

+1 at start, -1 at end
Ends before starts on ties
O(n log n)

Deep dive

The sweep line is the template for 'how many at once' questions.

Tie order encodes the touching rule: (time, -1) sorts before (time, +1).

The heap version also tells you which room each booking can reuse.

Python solution Ran on Python 3.13.5 · mypy --strict

Python 3.13

def rooms_needed(bookings: list[list[int]]) -> int:
    events: list[tuple[int, int]] = []
    for start, end in bookings:
        events.append((start, 1))
        events.append((end, -1))  # ends sort before starts at a tie
    in_use = most = 0
    for _, change in sorted(events):
        in_use += change
        most = max(most, in_use)
    return most

Kotlin Ran on Kotlin 2.4.21 · JDK 21.0.12.1

Kotlin 2.4

fun roomsNeeded(bookings: List<List<Int>>): Int {
    val events = mutableListOf<Pair<Int, Int>>()
    for (b in bookings) {
        events.add(b[0] to 1)
        events.add(b[1] to -1) // ends sort before starts at a tie
    }
    var inUse = 0
    var most = 0
    val order = events.sortedWith(
        compareBy({ it.first }, { it.second }))
    for ((_, change) in order) {
        inUse += change
        most = maxOf(most, inUse)
    }
    return most
}

Common mistakes

Sorting starts before ends at equal times, which over-counts.
Counting overlaps pairwise, which is O(n²) and not the same thing.

Senior take & follow-ups

Explain the tie rule; it shows you thought about edges.

Follow-up questions

Think of your answer first, then open the hint.

How do you assign actual rooms?
Show hint
Sort by start and keep a heap of (end, room); reuse the room with the earliest end if it is free.
What if bookings are huge in number but times are small integers?
Show hint
A difference array over time, then a prefix sum.

Similar on iOS: OperationQueue vs GCD The iOS page caps how many operations run at once; this page computes how many bookings run at once from their start and end times.

What each operation costs: Merge Sort · Quick Sort

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.