Compute minimum number of rooms needed
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
You are given a list of meetings, each with a start time and end time. A single room can host only one meeting at a time.
Two meetings **overlap** if one starts before the other ends (treat meetings as half-open intervals **[start, end)** so a meeting ending at time `t` does not conflict with another starting at time `t`).
### Task
Return the **minimum number of rooms** required to host all meetings.
### Input
- `intervals`: an array of `n` pairs `[start, end]` where `0 <= start <= end`.
### Output
- An integer: the minimum number of rooms needed.
### Constraints (typical interview bounds)
- `1 <= n <= 200000`
- Times are integers in a reasonable range (e.g., `0 .. 10^9`).
### Example
- Input: `[[0,30],[5,10],[15,20]]`
- Output: `2`
(One room can host `[0,30]`, the other can host `[5,10]` then `[15,20]`.)
Quick Answer: This question evaluates a candidate's ability to reason about overlapping intervals and resource allocation, testing algorithmic problem-solving skills and familiarity with data structures for scheduling conflicts.
You are given a list of meetings, where each meeting is represented as [start, end]. A single room can host only one meeting at a time. Meetings are treated as half-open intervals [start, end), so 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 all meetings. If start == end, the meeting occupies no time and does not require a room.
Constraints
- 0 <= n <= 200000
- 0 <= start <= end <= 10^9
Examples
Input: ([[0,30],[5,10],[15,20]],)
Expected Output: 2
Explanation: [0,30] overlaps with both [5,10] and [15,20], so at most 2 rooms are needed at the same time.
Input: ([[7,10],[2,4],[4,7],[10,12]],)
Expected Output: 1
Explanation: These meetings only touch at endpoints, so one room can host all of them in sequence.
Hints
- Try turning each meeting into two events: one when it starts and one when it ends.
- Because intervals are half-open, if a meeting ends at the same time another starts, process the ending event first.