Minimum Number of Rooms to Host a Set of Possibly Overlapping Meetings
Company: ByteDance
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are given the start and end times of a set of meetings. Every meeting must be held in a room, and a room can host only one meeting at a time. Return the minimum number of rooms needed to hold all of the meetings.
### Function Signature
```python
def min_rooms(meetings: list[tuple[int, int]]) -> int:
```
Each meeting is a pair `(start, end)`.
### Rules
- A meeting occupies its room during the half-open interval `[start, end)`: from `start` up to, but not including, `end`.
- Two meetings can use the same room only if their intervals do not overlap. A meeting that ends at time `t` and another that starts at time `t` do not overlap, so one room can host them back to back.
- Meetings are given in no particular order, and identical meetings can appear more than once; each occurrence is a separate meeting that needs its own room time.
- Return `0` if there are no meetings.
### Constraints
- `0 <= len(meetings) <= 10^5`
- `0 <= start < end <= 10^9` for every meeting
### Examples
**Example 1**
```text
Input: meetings = [(1, 5), (2, 6), (4, 8), (6, 9)]
Output: 3
```
At time 4, the meetings `(1, 5)`, `(2, 6)` and `(4, 8)` are all in progress, so at least three rooms are needed. Three are enough: `(6, 9)` starts after `(1, 5)` has ended and can use its room.
**Example 2**
```text
Input: meetings = [(1, 3), (3, 5), (5, 7)]
Output: 1
```
Each meeting starts exactly when the previous one ends, so one room hosts all three.
**Example 3**
```text
Input: meetings = [(10, 20), (10, 20), (20, 30)]
Output: 2
```
The two identical meetings need separate rooms, and `(20, 30)` can reuse either of them.
Overview: Given meetings as half-open start and end time intervals, compute the minimum number of rooms needed so that no room ever hosts two overlapping meetings. Tests interval reasoning, correct handling of back-to-back meetings that share an endpoint, and an efficient approach for up to 100,000 meetings.
You are given the start and end times of a set of meetings. Every meeting must be held in a room, and a room can host only one meeting at a time. Return the minimum number of rooms needed to hold all of the meetings.
Implement `min_rooms(meetings)`, where `meetings` is a list of pairs `[start, end]`, one pair per meeting. The function returns a single integer.
### Rules
- A meeting occupies its room during the half-open interval `[start, end)`: from `start` up to, but not including, `end`.
- Two meetings can use the same room only if their intervals do not overlap. A meeting that ends at time `t` and another that starts at time `t` do not overlap, so one room can host them back to back.
- Meetings are given in no particular order, and identical meetings can appear more than once; each occurrence is a separate meeting that needs its own room time.
- Return `0` if there are no meetings.
All times and the answer fit in a signed 32-bit integer.
### Constraints
- `0 <= len(meetings) <= 10^5`
- `0 <= start < end <= 10^9` for every meeting
### Examples
**Example 1**
```text
Input: meetings = [[1, 5], [2, 6], [4, 8], [6, 9]]
Output: 3
```
At time 4, the meetings `[1, 5]`, `[2, 6]` and `[4, 8]` are all in progress, so at least three rooms are needed. Three are enough: `[6, 9]` starts after `[1, 5]` has ended and can use its room.
**Example 2**
```text
Input: meetings = [[10, 20], [10, 20], [20, 30]]
Output: 2
```
The two identical meetings need separate rooms, and `[20, 30]` can reuse either of them, because a meeting that ends at 20 does not overlap one that starts at 20.
Constraints
- 0 <= len(meetings) <= 10^5
- 0 <= start < end <= 10^9 for every meeting
- Each meeting is a pair [start, end] occupying the half-open interval [start, end)
- Meetings are in no particular order; identical meetings may repeat and each occurrence counts separately
- All times and the answer fit in a signed 32-bit integer
Examples
Input: ([],)
Expected Output: 0
Explanation: No meetings need no rooms.
Input: ([[3, 7]],)
Expected Output: 1
Explanation: A single meeting needs exactly one room.
Hints
- At any moment, every meeting in progress needs its own room. What lower bound does that give, and can it always be met?
- Because the intervals are half-open, a meeting that ends at time t and one that starts at time t can share a room. Make sure equal times are handled that way.
- The input is unsorted and may contain identical meetings; each copy is a separate meeting.