Find the Minimum Number of Meeting Rooms
Company: ByteDance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Find the Minimum Number of Meeting Rooms
You are given meeting intervals `[start, end]`, where `start < end`. A room can host at most one meeting at a time, and a meeting ending at time `t` does not conflict with another meeting starting at time `t`.
Return the minimum number of rooms required to host every meeting.
## Function Signature
```python
def minimum_meeting_rooms(intervals: list[list[int]]) -> int:
...
```
## Constraints
- `0 <= len(intervals) <= 200_000`
- Every interval contains exactly two integer times between `-1_000_000_000` and `1_000_000_000`, inclusive.
- `start < end` for every meeting.
- Input intervals may be unsorted and may share start or end times.
## Examples
```text
Input: intervals = [[0, 30], [5, 10], [15, 20]]
Output: 2
```
```text
Input: intervals = [[7, 10], [10, 12]]
Output: 1
```
```text
Input: intervals = []
Output: 0
```
Overview: Find the minimum number of rooms needed for unsorted meeting intervals, with an ending meeting allowed to share a room with one starting at the same time. Practice sweep-line or heap reasoning, precise tie handling, overlapping intervals, duplicate boundaries, empty input, and large-scale time complexity.
You are given a list of meeting intervals. Each element is a pair `[start, end]` with `start < end`, meaning the meeting occupies a room from time `start` up to time `end`.
A room can host at most one meeting at a time. A meeting that ends at time `t` does **not** conflict with another meeting that starts at time `t`: the room is free again the instant the first meeting ends, so a single room can host both.
Return the minimum number of rooms needed so that every meeting can take place.
## Function
```
minimum_meeting_rooms(intervals)
```
## Input
- `intervals` is a list of two-element integer lists `[start, end]`.
- The meetings may be listed in any order, and two meetings may share a start time, an end time, or both. Two meetings may also be completely identical.
## Output
Return a single integer: the largest number of meetings that are in progress at the same instant. That number is exactly the minimum number of rooms required.
Because a meeting is treated as occupying its room over the half-open span `[start, end)`, meetings that merely touch — one ending exactly where the next begins — can share a room. With no meetings at all the answer is `0`.
The answer is one integer, so there is nothing to order or tie-break, and there is exactly one correct output for any input.
## Constraints
- `0 <= len(intervals) <= 200000`
- Every interval contains exactly two integer times between `-1000000000` and `1000000000`, inclusive.
- `start < end` for every meeting.
- Input intervals may be unsorted and may share start or end times.
- Every time is at most `1000000000` in magnitude and the answer is at most `len(intervals) <= 200000`, so nothing in this problem approaches a 32-bit integer limit or a JavaScript precision limit; `int` is the correct width in Java and C++.
- Do not mutate `intervals`.
## Examples
**Example 1**
```
Input: intervals = [[0, 30], [5, 10], [15, 20]]
Output: 2
```
`[0, 30]` occupies a room for the whole window. `[5, 10]` needs a second room, and once it ends that same second room is free for `[15, 20]`. Two rooms are enough.
**Example 2**
```
Input: intervals = [[7, 10], [10, 12]]
Output: 1
```
The second meeting starts exactly when the first ends, which is not a conflict, so one room hosts both.
**Example 3**
```
Input: intervals = []
Output: 0
```
With no meetings, no rooms are needed.
Constraints
- 0 <= len(intervals) <= 200000
- Every interval contains exactly two integer times between -1000000000 and 1000000000, inclusive.
- start < end for every meeting.
- Input intervals may be unsorted and may share start or end times; two meetings may be completely identical.
- A meeting ending at time t does not conflict with a meeting starting at time t, so a room is reusable the instant it is freed.
- Every time is at most 1000000000 in magnitude and the answer is at most len(intervals) <= 200000, so no quantity approaches a 32-bit integer limit or a JavaScript precision limit; `int` is the correct width in Java and C++.
- `intervals` must not be mutated.
Examples
Input: ([[0, 30], [5, 10], [15, 20]],)
Expected Output: 2
Explanation: Source example 1, carried over verbatim. [0, 30] runs the whole time, and [5, 10] then [15, 20] each need a second room while it is busy. Those two never overlap each other, so a second room is enough and the answer is 2.
Input: ([[7, 10], [10, 12]],)
Expected Output: 1
Explanation: Source example 2, carried over verbatim. The second meeting starts exactly when the first ends, and the statement says that is not a conflict, so one room hosts both. This is the case that separates the intended reading from the naive one, which would answer 2.
Hints
- The answer is not about which meeting goes in which room. Ask instead: across the whole timeline, what is the largest number of meetings happening at the same instant?
- Once you are counting concurrency, the pairing between a start and its own end stops mattering -- only how many starts and how many ends you have passed. Two separately sorted lists of times are enough to sweep.
- Decide deliberately what happens when a start and an end land on the same timestamp, and test that decision against `[[7, 10], [10, 12]]` and against a long back-to-back chain. Getting that one comparison backwards is the difference between the right answer and an answer that is too large by one on every chain.