# The Meeting Room Allocator

> Meetings overlap on the calendar. Rooms are limited.

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

Domain: Python · Difficulty: hard · Seniority: L5

## Problem

Given meetings as a list of [start, end] intervals, return the minimum number of rooms needed so no two meetings in the same room overlap. Intervals are half-open [start, end): a meeting ending at t does not conflict with one starting at t.

## Worked solution and explanation

### Why this problem exists in real interviews

This is a classic **interval scheduling** problem that tests whether candidates can decompose overlapping intervals into events and use a sweep-line approach. It probes greedy algorithm design and the ability to find peak concurrency.

> **Trick to Solving**
>
> Decompose each interval into two events: a +1 at the start time and a -1 at the end time. Sorting these events and sweeping through them gives the peak overlap, which equals the minimum number of rooms. Because intervals are half-open, end events at time t are processed before start events at time t.

---

### Break down the requirements

#### Step 1: Create start and end events

For each `[start, end]` interval, create two events: `(start, +1)` and `(end, -1)`.

#### Step 2: Sort events by time

When times are equal, process end events (-1) before start events (+1) because intervals are half-open.

#### Step 3: Sweep through events tracking concurrent meetings

Maintain a running count. Add the event delta at each step. The peak count is the answer.

---

### The solution

**Event sweep-line for peak overlap**

```python
def min_rooms(intervals):
    events = []
    for start, end in intervals:
        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.

> **Interviewers Watch For**
>
> Do you handle the half-open interval correctly? A meeting ending at time 10 must not conflict with one starting at 10. Sorting `(10, -1)` before `(10, 1)` handles this automatically since -1 < 1.

> **Common Pitfall**
>
> Using a min-heap approach without understanding why the sweep-line is simpler. Both work, but the event-based approach is easier to implement correctly and explain.

---

## 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/the_meeting_room_allocator)
- [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). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.