Minimum Number of Rooms to Host Overlapping Meetings
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given the schedule of `n` meetings for a single day. Meeting `i` occupies the half-open time interval `[start_i, end_i)`: it starts at `start_i` and its room becomes free exactly at `end_i`. A room can host only one meeting at a time, and meetings cannot be moved, shortened or split. Return the minimum number of rooms needed so that every meeting takes place at its scheduled time.
### Function Signature
```python
def min_rooms(meetings: List[List[int]]) -> int:
```
### Rules
- `meetings[i] = [start_i, end_i]`.
- A meeting that ends at time `t` and a meeting that starts at time `t` do not overlap, so they can use the same room.
- The input is not sorted and may contain identical meetings; each one needs its own room while it runs.
- Return `0` when there are no meetings.
### Constraints
- `0 <= n <= 10^5`
- `0 <= start_i < end_i <= 10^9`
### Examples
**Example 1**
```
meetings = [[1, 5], [2, 6], [5, 8], [9, 12]]
output = 2
```
The first two meetings overlap during `[2, 5)`. The meeting that starts at 5 can take the room freed at 5, and the last meeting starts after every other meeting has ended.
**Example 2**
```
meetings = [[3, 7], [3, 7], [3, 7]]
output = 3
```
**Example 3**
```
meetings = [[10, 20]]
output = 1
```
Overview: A scheduling problem that asks for the fewest rooms needed to hold a set of meetings given as half-open time intervals, where a room freed at a given moment can be reused immediately. It tests interval reasoning, correct handling of shared endpoints and duplicates, and an efficient solution for large inputs.
Read the full Microsoft Software Engineer interview experience this question came from