Compute the Minimum Number of Meeting Rooms
Company: Walmart
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Compute the Minimum Number of Meeting Rooms
### Problem
Implement `minimumMeetingRooms(intervals) -> rooms`.
Each interval is a two-element integer array `[start, end]` representing a half-open meeting interval `[start, end)`. A room can host another meeting beginning exactly when its previous meeting ends. Return the minimum number of rooms needed to schedule every meeting.
Do not mutate `intervals`.
### Constraints
- `0 <= intervals.length <= 200,000`.
- `-1,000,000,000 <= start < end <= 1,000,000,000`.
- Return `0` for an empty input.
- Target `O(n log n)` time and `O(n)` auxiliary space or better.
```hint Define the tie at one timestamp
Before implementing a sweep, decide whether an ending meeting or a starting meeting must be processed first when their timestamps are equal.
```
### Examples
```text
intervals = [[0, 30], [5, 10], [15, 20]]
rooms = 2
```
```text
intervals = [[1, 5], [5, 8], [8, 10]]
rooms = 1
```
```text
intervals = []
rooms = 0
```
### Discussion Requirements
- Explain a sorted start/end approach and a line-sweep event approach.
- State why end events must precede start events at the same timestamp for half-open intervals.
- Compare the event-array method with a min-heap of current meeting end times.
Quick Answer: Compute the minimum rooms required for half-open meeting intervals, allowing a new meeting to begin exactly as another ends. This algorithm question tests event tie semantics, overlap accounting, empty input, nonmutation, asymptotic performance, and comparison of sweep-based and active-end-time approaches.
Implement `minimumMeetingRooms(intervals) -> rooms`.
Each element of `intervals` is a two-element integer array `[start, end]` describing a
half-open meeting interval `[start, end)`. A single room may host another meeting that
begins exactly when its previous meeting ends, because the previous meeting no longer
occupies the room at time `end`. Return the minimum number of rooms required to schedule
every meeting.
Do not mutate `intervals`.
### Output
Return a single integer: the smallest room count that suffices. This equals the maximum
number of meetings that are simultaneously in progress at any instant. The answer is
unique, so no ordering or tie-breaking rule is needed. Return `0` when `intervals` is
empty.
### Constraints
- `0 <= intervals.length <= 200,000`
- `intervals[i].length == 2`
- `-1,000,000,000 <= start < end <= 1,000,000,000` (the inequality between the two
elements of a pair is strict: zero-length and inverted intervals never appear)
- Duplicate intervals may appear.
- Every input value and the returned count fit in a signed 32-bit integer, so `int` is
sufficient in Java and C++; no 64-bit arithmetic is required.
- Target `O(n log n)` time and `O(n)` auxiliary space or better.
### Examples
Example 1:
```text
intervals = [[0, 30], [5, 10], [15, 20]]
rooms = 2
```
`[0, 30)` overlaps both `[5, 10)` and `[15, 20)`, so two rooms are needed. `[5, 10)` and
`[15, 20)` are disjoint and can share the second room.
Example 2:
```text
intervals = [[1, 5], [5, 8], [8, 10]]
rooms = 1
```
Each meeting starts exactly when the previous one ends. Because the intervals are
half-open, no two meetings are ever in progress at the same instant, so one room hosts
all three.
Example 3:
```text
intervals = []
rooms = 0
```
Constraints
- 0 <= intervals.length <= 200,000
- intervals[i].length == 2
- -1,000,000,000 <= start < end <= 1,000,000,000
- Duplicate intervals may appear
- Every value and the returned count fit in a signed 32-bit integer
- Return 0 for an empty input
- intervals must not be mutated
- Target O(n log n) time and O(n) auxiliary space or better
Examples
Input: ([],)
Expected Output: 0
Input: ([[7, 9]],)
Expected Output: 1
Hints
- You never have to decide which physical room hosts which meeting. Ask instead: at any single instant, how many meetings are in progress at once?
- A start time and an end time only matter as events on a timeline; they do not have to stay attached to the interval they came from.
- The intervals are half-open, so decide deliberately which of an ending meeting and a starting meeting is processed first when their timestamps are equal. Example 2 is the case that punishes the wrong choice.