Minimum number of meeting rooms for a set of meetings
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
Given the start and end times of a set of meetings, return the minimum number of rooms needed to hold all of them, where a room can host only one meeting at a time. The report describes this round as a variant of the classic minimum-rooms problem without saying what the variant changed; this is the base problem.
### Function Signature
```python
def min_meeting_rooms(meetings: list[list[int]]) -> int:
```
### Rules
- `meetings[i] = [start, end]` occupies a room for the half-open interval `[start, end)`: the room is in use at every time `t` with `start <= t < end`.
- A meeting that ends at time `t` frees its room for a meeting that starts at time `t`.
- Identical meetings are separate meetings, and each needs its own room.
- Return `0` when there are no meetings.
### Constraints
- `0 <= len(meetings) <= 10^5`
- `0 <= start < end <= 10^9` for every meeting
- Times are integers, so every value fits in a 32-bit signed integer.
- `meetings` is in no particular order.
### Examples
**Example 1**
```text
Input: meetings = [[9, 12], [10, 13], [11, 12], [12, 14]]
Output: 3
```
At time `11`, the meetings `[9, 12)`, `[10, 13)` and `[11, 12)` are all in progress. At time `12`, two of them have ended, so `[12, 14)` can reuse a room.
**Example 2**
```text
Input: meetings = [[1, 5], [5, 8], [8, 9]]
Output: 1
```
Each meeting starts exactly when the one before it ends, so a single room hosts all three.
**Example 3**
```text
Input: meetings = [[4, 6], [1, 10], [6, 8], [2, 3]]
Output: 2
```
The meeting `[1, 10)` keeps one room busy throughout. The other three never overlap one another, so a second room hosts them in turn.
Overview: Given meeting start and end times as half-open intervals, return the minimum number of rooms needed so that no two overlapping meetings share a room. It tests interval reasoning, sorting and careful handling of meetings that end exactly when others start.
Given the start and end times of a set of meetings, return the minimum number of rooms needed to hold all of them. A room can host only one meeting at a time.
Implement `min_meeting_rooms(meetings)`, where `meetings[i] = [start, end]`, and return the minimum number of rooms as an integer.
### Rules
- Meeting `[start, end]` occupies a room for the half-open interval `[start, end)`: the room is in use at every time `t` with `start <= t < end`.
- A meeting that ends at time `t` frees its room for a meeting that starts at time `t`.
- Identical meetings are separate meetings, and each needs its own room.
- Return `0` when there are no meetings.
### Constraints
- `0 <= len(meetings) <= 10^5`
- Each `meetings[i]` is a pair `[start, end]` of integers.
- `0 <= start < end <= 10^9` for every meeting
- Times are integers, so every value fits in a 32-bit signed integer; the answer is at most `10^5`, so no value exceeds `2^31 - 1` (Java and C++ use `int`).
- `meetings` is in no particular order.
### Example 1
```text
Input: meetings = [[9, 12], [10, 13], [11, 12], [12, 14]]
Output: 3
```
At time `11`, the meetings `[9, 12)`, `[10, 13)` and `[11, 12)` are all in progress. At time `12`, two of them have ended, so `[12, 14)` can reuse a room.
### Example 2
```text
Input: meetings = [[4, 6], [1, 10], [6, 8], [2, 3]]
Output: 2
```
The meeting `[1, 10)` keeps one room busy throughout. The other three never overlap one another (`[4, 6)` ends exactly when `[6, 8)` starts), so a second room hosts them in turn.
Constraints
- 0 <= len(meetings) <= 10^5
- Each meetings[i] is a pair [start, end] of integers
- 0 <= start < end <= 10^9 for every meeting
- Times are integers, so every value fits in a 32-bit signed integer (no value exceeds 2^31 - 1)
- meetings is in no particular order
Examples
Input: ([],)
Expected Output: 0
Explanation: No meetings need no rooms (minimum valid input).
Input: ([[5, 10]],)
Expected Output: 1
Explanation: A single meeting needs exactly one room.
Hints
- A meeting [start, end) is in progress at time t only when start <= t < end, so a meeting ending at t and one starting at t never need a room at the same moment.
- The list can arrive shuffled or even reverse-sorted, so do not rely on the input order.
- Ask how many meetings can be in progress at a single instant, and how that number relates to the number of rooms.