# Meeting Rooms II

[link](https://leetcode.com/problems/meeting-rooms-ii/) · Medium · `array`, `sorting`, `two pointers`, `sweep line`, `heap`

> "how many things are active at the same time" / "minimum resources so nothing clashes" → peak overlap. Sort the start times and the end times separately and sweep with two pointers (or sort ±1 events). Pairing doesn't matter, only the order of events. Decide the tie rule explicitly: end-before-start when touching intervals don't overlap.

## Problem

> *From a coding assessment (2026-10-13), where it was called "Minimum meeting rooms". Same
> problem as LeetCode #253 Meeting Rooms II.*
>
> Given `n` meetings as `[start, end]`, return the minimum number of rooms so that no two
> meetings in the same room overlap. A meeting ending at time `t` and one starting at `t` do
> **not** overlap, so they can share a room.

**Example 1**
```
Input:  meetingTimings = [[1, 4], [1, 5], [5, 6], [6, 10], [7, 9]]
Output: 2
```

**Constraints**
- `1 <= n <= 2 * 10^5`
- `1 <= start <= end <= 2 * 10^6`

## Thinking

- **Brute force idea:** the busiest moment is always at some meeting's start, so for each start
  `s` count the meetings with `start <= s < end`: $O(n^2)$. Too slow at $n = 2 \cdot 10^5$.
- **Key insight:** every meeting running at the same moment needs its own room, and rooms can be
  reused freely, so **answer = peak number of overlapping meetings**. To find the peak you don't
  need to know which start goes with which end: two sorted timelines are enough, one for "a
  meeting begins" and one for "a room frees up". Sweep them with two pointers.
- **Tie rule:** a meeting ending at 5 hands its room to one starting at 5, so at equal times the
  **end is processed first** (`ends[j] <= s`, not `<`).
- **Edge cases to remember:** a single meeting, touching meetings (`[1,5]`, `[5,6]` → 1 room),
  identical meetings (all need separate rooms), one long meeting covering many short ones.
  **Zero-length meetings** (`start == end`, allowed by the constraints) are ambiguous: the sweep
  treats them as needing no room, the heap gives them one (see section 5).

## Solution

### Approach A — my version: sorted starts and ends, two pointers ✅ best practice

**Complexity:** Time $O(n \log n)$ (sorting; the loop is $O(n)$ because `j` only moves forward)
· Space $O(n)$.
`j` points at the earliest meeting that hasn't ended yet. For each start, release every meeting
with `end <= s`, then take a room for the new one and record the peak.

```python
def min_meeting_rooms(meetings: list[list[int]]) -> int:
    starts = sorted(m[0] for m in meetings)
    ends = sorted(m[1] for m in meetings)

    rooms = max_rooms = j = 0
    for s in starts:
        # free every room whose meeting ended by this start time
        while j < len(ends) and ends[j] <= s:
            j += 1
            rooms -= 1
        rooms += 1
        max_rooms = max(max_rooms, rooms)
    return max_rooms
```

### Approach B — brute force: count overlaps at every start

**Complexity:** Time $O(n^2)$ · Space $O(1)$.
The peak is reached at some start time, so check each one. Only useful as a reference to test
the others against.

```python
def min_meeting_rooms_brute(meetings: list[list[int]]) -> int:
    return max(sum(a <= s < b for a, b in meetings) for s, _ in meetings)
```

### Approach C — sort by start, min-heap of end times

**Complexity:** Time $O(n \log n)$ · Space $O(n)$.
The heap holds the end time of every room in use. If the room that frees up earliest is free by
this start, reuse it (pop), then push this meeting's end. The heap's final size is the answer.
Same speed, slightly more code, and it extends naturally to "which room does each meeting get".

```python
import heapq

def min_meeting_rooms_heap(meetings: list[list[int]]) -> int:
    ends: list[int] = []                     # end times of rooms in use
    for start, end in sorted(meetings):
        if ends and ends[0] <= start:        # earliest-ending room is free again
            heapq.heapreplace(ends, end)
        else:
            heapq.heappush(ends, end)
    return len(ends)
```

## Scratch / Experiments

### Zero-length meetings

The constraints allow `start == end`. The sweep processes the end before the start at equal
times, so a zero-length meeting gives its room back before taking it: it never counts. The heap
always pushes it, so it gets a room. If the grader expects a room for every meeting, use the heap.

```python
for meetings in ([[5, 5]], [[5, 5], [5, 5]], [[1, 10], [5, 5]]):
    print(meetings, {fn.__name__: fn(meetings) for fn in APPROACHES})
```

### Timing

Max size $n = 2 \cdot 10^5$ random meetings for A and C; the brute force is $O(n^2)$, so it gets
$n = 2000$, where it is already ~400× slower than the others.

Typical results:

| Approach | $n = 2000$ | $n = 2 \cdot 10^5$ |
|---|---|---|
| A two pointers ✅ | ~0.5 ms | ~100 ms |
| B brute force | ~190 ms | (~30 min) |
| C min-heap | ~0.5 ms | ~190 ms |

A and C are both $O(n \log n)$ and tie at small $n$. At full size A is about twice as fast: it sorts two flat lists of ints
(fast C comparisons) while C sorts lists of pairs (each comparison compares lists) and then does
a Python-level heap operation per meeting.

```python
import random

random.seed(0)
def random_meetings(n):
    out = []
    for _ in range(n):
        s = random.randint(1, 2_000_000 - 1)
        out.append([s, random.randint(s + 1, min(s + 50_000, 2_000_000))])
    return out

small, big = random_meetings(2000), random_meetings(200_000)
for fn in APPROACHES:
    print(f"{fn.__name__:26s} n=2000 ", end=" ")
    %timeit fn(small)
for fn in (min_meeting_rooms, min_meeting_rooms_heap):
    print(f"{fn.__name__:26s} n=2e5  ", end=" ")
    %timeit fn(big)
```

## Takeaways

- **Pattern:** "how many things are active at the same time" / "minimum resources so nothing
  clashes" → **peak overlap**. Sort the start times and the end times separately and sweep with
  two pointers (or sort ±1 events). Pairing doesn't matter, only the order of events. Decide the
  **tie rule** explicitly: end-before-start when touching intervals don't overlap.
- **Mistakes to avoid:**
  - Using `<` instead of `<=` when releasing rooms: touching meetings would then need two rooms.
  - Assuming the input is sorted: both approaches sort first.
  - Not checking what the constraints allow: `start <= end` means zero-length meetings exist,
    and the sweep and the heap answer them differently.
- **Alternatives:** the min-heap (Approach C) when you also need to assign rooms; a difference
  array over the time range ($O(n + T)$, $T = 2 \cdot 10^6$) when times are small integers.
- **Related problems:** Meeting Rooms (#252, can one person attend all = peak ≤ 1), Merge
  Intervals (#56, sort by start), Non-overlapping Intervals (#435, greedy by end), Car Pooling
  (#1094, same sweep with passenger counts), My Calendar II (#731), Minimum Number of Arrows to
  Burst Balloons (#452).

---

From https://taosu.blog/notes/0253-meeting-rooms-ii