Minimum Number of Rooms to Schedule Overlapping Meetings
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a list of meetings, where `meetings[i] = [start, end]` means meeting `i` occupies the half-open time interval `[start, end)`. Every meeting must be held in one room for its whole interval, and two meetings can share a room only if their intervals do not overlap.
Return the minimum number of rooms needed to hold all the meetings.
### Function Signature
```python
def min_meeting_rooms(meetings: list[list[int]]) -> int:
```
### Rules
- Intervals are half-open: a meeting that ends at time `t` and a meeting that starts at time `t` do not overlap and may use the same room.
- Meetings are given in no particular order. Identical intervals are separate meetings, and each needs its own room.
- An empty list needs `0` rooms.
### Constraints
- `0 <= len(meetings) <= 10^5`
- Each `meetings[i]` contains exactly two integers with `0 <= start < end <= 10^9`.
- The result is an integer from `0` to `len(meetings)` inclusive.
### Examples
**Example 1**
- Input: `meetings = [[1, 10], [2, 6], [7, 12]]`
- Output: `2`
- Explanation: `[1, 10)` overlaps both other meetings, so it needs a room of its own. `[2, 6)` ends before `[7, 12)` starts, so those two can share a second room.
**Example 2**
- Input: `meetings = [[4, 8], [8, 12], [1, 4]]`
- Output: `1`
- Explanation: In time order the meetings are `[1, 4)`, `[4, 8)` and `[8, 12)`, each starting exactly when the previous one ends, so one room is enough.
**Example 3**
- Input: `meetings = [[1, 5], [2, 6], [3, 7], [5, 9]]`
- Output: `3`
- Explanation: During `[3, 5)` the first three meetings are all in progress, so at least three rooms are needed. Three are enough, because `[5, 9)` can use the room that `[1, 5)` frees at time `5`.
Overview: Given meetings as half-open time intervals, find the smallest number of rooms needed so that no two meetings sharing a room overlap. Tests interval reasoning, correct handling of back-to-back meetings and duplicates, and an efficient solution for up to 100,000 meetings.
Read the full Google Software Engineer interview experience this question came from
You manage a shared pool of conference rooms. You are given `meetings`, where `meetings[i] = [start_i, end_i]` means meeting `i` occupies the half-open time interval `[start_i, end_i)`. Each meeting must be held in a single room for its entire interval, and two meetings may use the same room only if their intervals do not overlap.
Return the minimum number of rooms needed so that every meeting can be held.
### Rules
- Intervals are half-open: a meeting that ends at time `t` and a meeting that starts at time `t` do not overlap and may use the same room.
- Meetings are given in no particular order.
- Identical intervals are separate meetings, and each needs its own room.
- An empty list needs `0` rooms.
### Constraints
- `0 <= len(meetings) <= 10^5`
- Each `meetings[i]` contains exactly two integers, `start_i` and `end_i`, with `0 <= start_i < end_i <= 10^9`.
- The answer is an integer from `0` to `len(meetings)` inclusive.
- Every input and output value fits in a 32-bit signed integer (at most `10^9 < 2^31 - 1`), so `int` is sufficient in Java and C++.
### Example 1
```text
Input: meetings = [[1, 10], [2, 6], [7, 12]]
Output: 2
```
`[1, 10)` overlaps both other meetings, so it needs a room of its own. `[2, 6)` ends before `[7, 12)` starts, so those two can share a second room.
### Example 2
```text
Input: meetings = [[4, 8], [8, 12], [1, 4]]
Output: 1
```
In time order the meetings are `[1, 4)`, `[4, 8)` and `[8, 12)`. Each one starts exactly when the previous one ends, so a single room is enough.
Implement `min_meeting_rooms(meetings)`, which returns the minimum number of rooms as an integer.
Constraints
- 0 <= len(meetings) <= 10^5
- meetings[i] = [start_i, end_i] contains exactly two integers
- 0 <= start_i < end_i <= 10^9
- Intervals are half-open: [start_i, end_i)
- The answer is an integer from 0 to len(meetings) inclusive; all values fit in a 32-bit signed integer.
Examples
Input: ([[1, 10], [2, 6], [7, 12]],)
Expected Output: 2
Explanation: Source example 1: [1, 10) overlaps both others, while [2, 6) and [7, 12) can share a room.
Input: ([[4, 8], [8, 12], [1, 4]],)
Expected Output: 1
Explanation: Source example 2: unsorted back-to-back chain; each meeting starts exactly when the previous ends, so one room suffices.
Hints
- The number of rooms you need equals the largest number of meetings that are in progress at the same moment. Why can you never do better, and why is that many always enough?
- You do not need to remember which meeting holds which room. Consider the start times and end times as two separate sorted lists.
- Be careful at shared boundaries: when one meeting ends at time t and another starts at t, the ending must be processed first so the room is freed.
Community answers
Answer by mojahidislam221
import java.util.*;
class Solution {
public int minMeetingRooms(int[][] meetings) {
if (meetings == null || meetings.length == 0) {
return 0;
}
// Sort meetings by start time
Arrays.sort(meetings, (a, b) -> Integer.compare(a[0], b[0]));
// Stores end times of meetings currently using rooms
PriorityQueue pq = new PriorityQueue<>();
int maxRooms = 0;
for (int[] meeting : meetings) {
int start = meeting[0];
int end = meeting[1];
// Reuse every room whose meeting has already ended.
while (!pq.isEmpty() && pq.peek() <= start) {
pq.poll();
}
// Current meeting needs a room.
pq.offer(end);
// Track maximum simultaneous rooms.
maxRooms = Math.max(maxRooms, pq.size());
}
return maxRooms;
}
}