No Vacancy

A hard Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
hard
Seniority
L5
Asked in
Uber

Problem

A room-booking service holds a day's calendar as meetings, a list of [start, end] intervals, and needs the fewest rooms that can host all of them without two live meetings sharing a room. Treat the intervals as half-open: a meeting ending at t frees its room for one starting at t, and an empty schedule needs zero rooms.

Every booking needs a room. Find the busiest moment.

Example 1

Input:

meetings = [[0,30],[5,10],[15,20]]

Output:

2

Example 2

Input:

meetings = [[7,10],[2,4]]

Output:

1

Worked solution and explanation

What this really is

Strip off the calendar costume and this is peak concurrency: at the single busiest instant, how many meetings are live at once. That count IS the room minimum, because two meetings need separate rooms exactly when they coexist. Almost everyone sees that much. What separates candidates is the boundary. Under half-open intervals a meeting ending at t and one starting at t do NOT collide, so if you order your events carelessly you count them as overlapping and report one room too many.

Break down the requirements

Step 1: Create start and end events

For each [start, end] interval, create two events: (start, +1) and (end, -1). You now have 2n events and the original pairing no longer matters.

Step 2: Sort events by time

Sort the (time, delta) tuples. The tie-break is the whole game: when two events share a timestamp, the -1 must land first so a back-to-back meeting reuses the freed room. Plain tuple sort gives you this for nothing since -1 sorts before 1.

Step 3: Sweep and track the peak

Walk the sorted events adding each delta to a running count. Track the maximum the count ever reaches. That peak is the minimum rooms; an empty input never enters the loop and returns 0.

The solution

Event sweep-line for peak overlap
def min_rooms(meetings):
    events = []
    for start, end in meetings:
        events.append((start, 1))
        events.append((end, -1))
    events.sort()
    current_rooms = 0
    max_rooms = 0
    for time, delta in events:
        current_rooms += delta
        if current_rooms > max_rooms:
            max_rooms = current_rooms
    return max_rooms

Common follow-up questions