Minimum number of rooms needed to hold overlapping meetings
Company: Oracle
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a list of meetings, each with a start time and an end time. A room can host at most one meeting at a time, and a meeting stays in the same room from its start to its end. Return the minimum number of rooms needed so that every meeting can be held in full.
### Function Signature
```python
def min_meeting_rooms(intervals: list[list[int]]) -> int:
```
`intervals[i] = [start, end]` describes meeting `i`, which occupies the half-open time interval `[start, end)`.
### Rules
- Two meetings conflict when their intervals overlap. A meeting that ends at time `t` does not conflict with a meeting that starts at time `t`, so the two can use the same room.
- The meetings are given in no particular order.
- Return `0` when the list is empty.
### Constraints
- `0 <= len(intervals) <= 10^5`
- `0 <= start < end <= 10^9` for every meeting
### Examples
**Example 1**
```text
Input: intervals = [[1, 5], [2, 6], [4, 8], [7, 9]]
Output: 3
```
Between times 4 and 5, the meetings `[1, 5)`, `[2, 6)` and `[4, 8)` are all in progress, so three rooms are needed. Three is enough: by time 7 the meeting `[2, 6)` has ended, so `[7, 9)` can use its room.
**Example 2**
```text
Input: intervals = [[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: intervals = [[10, 20], [0, 10], [5, 15]]
Output: 2
```
`[5, 15)` overlaps both other meetings, but `[0, 10)` and `[10, 20)` do not overlap each other and can share a room.
Overview: A coding question that asks for the minimum number of rooms needed so that every meeting in an unsorted list of half-open time intervals can be held without overlap. It tests reasoning about overlapping intervals, the boundary rule for meetings that end and start at the same time, and an efficient solution for large inputs.
Read the full Oracle Software Engineer interview experience this question came from
You are given a list of meetings. `intervals[i] = [start, end]` describes meeting `i`, which occupies the half-open time interval `[start, end)`. A room can host at most one meeting at a time, and a meeting stays in the same room from its start to its end. Return the minimum number of rooms needed so that every meeting can be held in full.
Implement `min_meeting_rooms(intervals)`, which returns that minimum as an integer.
### Rules
- Two meetings conflict when their intervals overlap. A meeting that ends at time `t` does not conflict with a meeting that starts at time `t`, so the two can use the same room.
- The meetings are given in no particular order, and the same interval may appear more than once.
- Return `0` when the list is empty.
### Constraints
- `0 <= len(intervals) <= 10^5`
- `0 <= start < end <= 10^9` for every meeting
- Every time value and the answer (at most `10^5`) fit in a signed 32-bit integer; no value exceeds `2^31 - 1`.
### Examples
**Example 1**
```text
Input: intervals = [[1, 5], [2, 6], [4, 8], [7, 9]]
Output: 3
```
Between times 4 and 5, the meetings `[1, 5)`, `[2, 6)` and `[4, 8)` are all in progress, so three rooms are needed. Three is enough: by time 7 the meeting `[2, 6)` has ended, so `[7, 9)` can use its room.
**Example 2**
```text
Input: intervals = [[10, 20], [0, 10], [5, 15]]
Output: 2
```
`[5, 15)` overlaps both other meetings, but `[0, 10)` and `[10, 20)` do not overlap each other and can share a room.
Constraints
- 0 <= len(intervals) <= 10^5
- 0 <= start < end <= 10^9 for every meeting intervals[i] = [start, end]
- Each meeting occupies the half-open interval [start, end); meetings are given in no particular order
- Every time value and the answer fit in a signed 32-bit integer
Examples
Input: ([[1, 5], [2, 6], [4, 8], [7, 9]],)
Expected Output: 3
Explanation: Source Example 1: [1,5), [2,6) and [4,8) are all in progress between 4 and 5; [7,9) reuses the room freed by [2,6).
Input: ([[10, 20], [0, 10], [5, 15]],)
Expected Output: 2
Explanation: Source Example 3, unsorted input: [0,10) and [10,20) touch and share a room; [5,15) overlaps both and needs a second room.
Hints
- If several meetings are all in progress at the same instant, each of them needs a different room. How does the largest such group relate to the answer?
- The set of meetings in progress only changes at a start time or an end time, so those are the only moments worth examining.
- A meeting ending at time t and another starting at time t may share a room; make sure two such meetings are never counted as running together.