Minimum Number of Rooms to Host All Meetings
Company: ByteDance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Meetings are held in a set of identical rooms. Each meeting needs one room for its whole duration, and a room can host only one meeting at a time. Return the minimum number of rooms needed to host every meeting.
### 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 meeting is in progress at every time `t` with `start <= t < end`.
- A room freed at time `t` can host another meeting that starts at time `t`.
- Identical meetings listed twice 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 = [[0, 6], [2, 4], [3, 8], [7, 9]]
Output: 3
```
At time `3`, the meetings `[0, 6)`, `[2, 4)` and `[3, 8)` are all in progress, so at least three rooms are needed. Three are enough: one room hosts `[0, 6)` and then `[7, 9)`, and the other two host `[2, 4)` and `[3, 8)`.
**Example 2**
```text
Input: meetings = [[1, 5], [5, 8], [8, 10]]
Output: 1
```
Each meeting starts exactly when the previous one ends, so one room hosts all three in turn.
**Example 3**
```text
Input: meetings = [[4, 9], [4, 9], [1, 3]]
Output: 2
```
The two copies of `[4, 9)` need separate rooms. The meeting `[1, 3)` ends before either starts, so it can use one of those two rooms.
Overview: A coding question that asks for the minimum number of rooms needed to host a set of meetings given as half-open time intervals, where a room freed at a moment can be reused at that same moment. It tests interval overlap reasoning, duplicate handling, and an efficient solution for large inputs.
Meetings are held in a set of identical rooms. Each meeting needs one room for its whole duration, and a room can host only one meeting at a time. Given the list `meetings`, return the minimum number of rooms needed to host every meeting.
Implement `min_meeting_rooms(meetings)`, which takes a list of `[start, end]` integer pairs and returns an integer.
### Rules
- `meetings[i] = [start, end]` occupies a room for the half-open interval `[start, end)`: the meeting is in progress at every time `t` with `start <= t < end`.
- A room freed at time `t` can host another meeting that starts at time `t`.
- Identical meetings listed twice 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. No time and no answer can exceed 2^31 - 1, so a 32-bit `int` is enough in Java and C++.
- `meetings` is in no particular order and may contain identical pairs.
### Example 1
```text
Input: meetings = [[0, 6], [2, 4], [3, 8], [7, 9]]
Output: 3
```
At time `3`, the meetings `[0, 6)`, `[2, 4)` and `[3, 8)` are all in progress, so at least three rooms are needed. Three are enough: one room hosts `[0, 6)` and then `[7, 9)`, and the other two host `[2, 4)` and `[3, 8)`.
### Example 2
```text
Input: meetings = [[4, 9], [4, 9], [1, 3]]
Output: 2
```
The two copies of `[4, 9)` need separate rooms. The meeting `[1, 3)` ends before either starts, so it can use one of those two rooms.
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; the answer is at most len(meetings)
- meetings is in no particular order and may contain identical pairs
Examples
Input: ([],)
Expected Output: 0
Explanation: No meetings need no rooms (minimum valid, empty list).
Input: ([[5, 10]],)
Expected Output: 1
Explanation: A single meeting needs exactly one room.
Hints
- Look at the instant when the most meetings are in progress at once. What does that number tell you about the answer?
- Intervals are half-open: a meeting that ends at time t and one that starts at time t never need a room at the same moment.
- The input is in no particular order, and identical meetings are separate meetings that each need their own room.