Compute the Minimum Number of Meeting Rooms
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
## Compute the Minimum Number of Meeting Rooms
### Problem
Implement `minimumMeetingRooms(intervals) -> roomCount`.
Each meeting is a half-open interval `[start, end)`. Return the minimum number of rooms needed so every meeting can run for its full interval. A room released at time `t` may be reused by a meeting starting at time `t`.
### Portable Contract
- `intervals` is a JSON array of two-integer arrays `[start, end]`.
- `0 <= intervals.length <= 12,000`.
- `0 <= start < end <= 9,000,000,000,000`; values remain exact in signed 64-bit and JavaScript integer arithmetic.
- Duplicate intervals are separate meetings.
- Empty input returns `0`.
- Do not modify `intervals`.
- Let `B` be the compact UTF-8 JSON byte length of `intervals`, counting all structural and numeric bytes. Inputs satisfy `B <= 160,000`; the result is an integer from `0` through `12,000`.
- Target `O(n log n)` time and `O(n)` auxiliary space, or better, for `n = intervals.length`.
Python and JavaScript receive arrays of integer pairs. Java may use `List<List<Long>>`, and C++ may use `vector<vector<long long>>`; return an integer room count.
```hint Count simultaneous activity
The required room count is determined by the largest number of intervals active at one time, not by the total number of conflicts.
```
```hint Resolve equal timestamps deliberately
At a shared timestamp, process the event that frees a half-open interval before the event that starts another one.
```
### Examples
```text
intervals = [[0, 30], [5, 10], [15, 20]]
roomCount = 2
```
```text
intervals = [[1, 5], [5, 9], [9, 12]]
roomCount = 1
```
### Discussion Requirements
- State the invariant represented by the active-room state.
- Explain how endpoint ordering implements half-open intervals.
- Compare a min-heap of room release times with separately sorted start and end arrays.
- Include tests for empty input, all meetings overlapping, touching chains, and duplicate intervals.
Quick Answer: Compute the fewest rooms needed to host a set of half-open meeting intervals. The challenge focuses on concurrent-activity tracking, precise treatment of equal timestamps, duplicate meetings, and comparison of efficient scheduling strategies.
Implement `minimumMeetingRooms(intervals) -> roomCount`.
Each meeting is a half-open interval `[start, end)`. Return the minimum number of rooms needed so that every meeting can run for its full interval. A room released at time `t` may be reused by a meeting starting at time `t`, so two meetings that merely touch at an endpoint never need two rooms.
### Input
`intervals` is a list of two-integer pairs `[start, end]`. It is not sorted. Duplicate pairs are distinct meetings and each one needs its own room while it runs. Do not modify `intervals`.
### Output
Return a single integer: the smallest number of rooms that can host every meeting. Empty input returns `0`. The answer is uniquely determined by the input -- it is the largest number of meetings that are simultaneously in progress at any instant.
### Example 1
```text
intervals = [[0, 30], [5, 10], [15, 20]]
roomCount = 2
```
`[0, 30)` runs the whole time; `[5, 10)` and `[15, 20)` never overlap each other, so both can share the second room.
### Example 2
```text
intervals = [[1, 5], [5, 9], [9, 12]]
roomCount = 1
```
The chain only touches at endpoints. The room freed at time `5` is taken immediately by the meeting starting at `5`, and again at time `9`.
### Language notes
Coordinates reach `9,000,000,000,000`, which is above `2^31 - 1`. Java receives `long[][]` and C++ receives `std::vector<std::vector<long long>>`; the returned count always fits in `int`. Every value stays exact in signed 64-bit and in IEEE-754 double arithmetic, and the algorithm only ever compares and counts coordinates, never sums them.
Constraints
- 0 <= intervals.length <= 12000
- Every element of intervals is exactly two integers [start, end]
- 0 <= start < end <= 9000000000000
- Coordinates exceed 2^31 - 1, so Java must use long and C++ must use long long; 9e12 is far below 2^53 so JavaScript numbers stay exact
- Duplicate intervals are separate meetings, each needing its own room while it runs
- Empty input returns 0
- intervals must not be modified
- Let B be the compact UTF-8 JSON byte length of intervals, counting all structural and numeric bytes; inputs satisfy B <= 160000
- The returned room count is an integer from 0 through 12000
- Target O(n log n) time and O(n) auxiliary space, or better, for n = intervals.length
Examples
Input: ([],)
Expected Output: 0
Explanation: Empty input: no meetings, so no rooms.
Input: ([[0, 1]],)
Expected Output: 1
Explanation: A single meeting always needs exactly one room.
Hints
- The answer is the largest number of meetings in progress at one instant, not the number of pairs that conflict. Eight meetings can form four conflicting pairs and still fit in two rooms.
- Intervals are half-open, so at a shared timestamp the release must be processed before the acquisition. Decide deliberately whether your comparison at the boundary is `<` or `<=`.
- Two standard shapes both reach O(n log n): a min-heap holding the release time of every busy room, or the start times and the end times sorted independently and then walked together.