# No Vacancy

> Every booking needs a room. Find the busiest moment.

Canonical URL: <https://datadriven.io/problems/no_vacancy>

Domain: Python · Difficulty: hard · Seniority: L5

## 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.

## 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.

> **Trick to solving**
>
> Forget the intervals as objects. Explode each `[start, end]` into a `+1` event at the start and a `-1` event at the end, sort the events, and sweep a running counter. The high-water mark of that counter is your answer. The half-open rule falls out for free: at an equal timestamp, sorting puts `(t, -1)` before `(t, 1)` because -1 < 1, so the room is released before the next meeting claims it.

---

### 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**

```python
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
```

> **Time and space complexity**
>
> **Time:** O(n log n), dominated by sorting the 2n events. **Space:** O(n) for the events list. The sweep itself is a single linear pass.

> **Interviewers watch for**
>
> The half-open boundary is the tell. A meeting ending at 10 must not conflict with one starting at 10, so a strong candidate states up front that `(10, -1)` sorts before `(10, 1)` and explains why. Candidates who hand-wave the tie-break almost always ship the off-by-one.

> **Common pitfall**
>
> Reaching for a min-heap of room end times when the sweep is simpler to write and to explain. The heap solution is correct and equally O(n log n), but on a whiteboard it gives you more places to make the boundary mistake. Pick the form you can defend.

---

## Common follow-up questions

- How would you also return which specific rooms each meeting is assigned to? _(Tests extending from counting to actual assignment using a min-heap of room end times.)_
- What if meetings had priorities and higher-priority meetings could preempt? _(Tests preemptive scheduling algorithms.)_
- How would this scale to millions of meetings across multiple offices? _(Tests partitioning by location and parallel processing.)_
- What if intervals were streaming in real time? _(Tests online algorithms vs batch processing trade-offs.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/no_vacancy)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.