Meeting Rooms III — Solution in Python, Java & C++
Meeting Rooms III solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem on arrays and sorting.
Meeting Rooms III is a hard coding problem on arrays, sorting and simulation, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Hard
- Topics: Arrays, Sorting, Simulation, Heap
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There are n meeting rooms numbered 0 … n - 1. meetings[i] = [start, end] is a half-open interval, and all the start times are different.
Meetings are handled in order of start time. A meeting takes the lowest-numbered free room. If every room is busy, it is delayed — keeping its original duration — until a room frees, and then takes the lowest-numbered room that frees earliest. Return the room that held the most meetings, breaking ties by the lowest number.
Example 1
Input: n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
Output: 0
Explanation: Both rooms hold two meetings, so the lower number wins.
Example 2
Input: n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
Output: 1
Example 3
Input: n = 1, meetings = [[0,5],[5,10]]
Output: 0
Constraints
1 <= n <= 1001 <= meetings.length <= 1000meetings[i].length == 20 <= start < end <= 5 * 10^5All the values of start are unique.
Hints for Meeting Rooms III
Hint 1
Process the meetings in order of start time.
Hint 2
A delayed meeting keeps its length, so it ends at
whenTheRoomFrees + (end - start).Hint 3
Two pools again: free rooms by number, busy rooms by the time they free.
How to solve Meeting Rooms III
Simulate. Sort by start time, and for each meeting either take the lowest-numbered free room or delay it into the room that frees soonest, extending its end by the meeting's original duration.
Approach
- Sort the meetings by start time.
- Free every room whose end time is at most the meeting's start.
- If a room is free, take the lowest-numbered one and set its end to the meeting's end.
- Otherwise find the earliest-freeing room — lowest number on ties — and set its end to
itsEnd + (end - start). - Count bookings per room and return the busiest, lowest number first.
Why it works
Keeping the original duration on a delayed meeting is the rule that makes the simulation non-trivial: a delayed meeting pushes its room's free time further out than the meeting's own end would suggest, which cascades into later decisions. Tie-breaking by room number in both branches is what makes the answer well defined.
Complexity
- Time —
O(m log m + m · n) as written, or O((m + n) log n) with two heaps - Space —
O(n)
Pitfalls
- A delayed meeting does not end at its original
end. - Rooms freeing exactly at the start time are available.
- Ties on the earliest free time go to the lower room number.
Reference solution
Python
from typing import List
import heapq
def mostBooked(n: int, meetings: List[List[int]]) -> int:
ordered = sorted(meetings, key=lambda m: m[0])
free = list(range(n))
heapq.heapify(free)
busy = []
count = [0] * n
for start, end in ordered:
while busy and busy[0][0] <= start:
_, room = heapq.heappop(busy)
heapq.heappush(free, room)
if free:
room = heapq.heappop(free)
heapq.heappush(busy, (end, room))
else:
done, room = heapq.heappop(busy)
heapq.heappush(busy, (done + (end - start), room))
count[room] += 1
best = 0
for i in range(1, n):
if count[i] > count[best]:
best = i
return bestJava
public static int mostBooked(int n, int[][] meetings) {
int[][] sorted = meetings.clone();
Arrays.sort(sorted, (a, b) -> a[0] - b[0]);
long[] freeAt = new long[n];
int[] count = new int[n];
for (int[] mt : sorted) {
long s = mt[0], e = mt[1];
int pick = -1;
for (int i = 0; i < n; i++) {
if (freeAt[i] <= s) { pick = i; break; }
}
if (pick >= 0) {
freeAt[pick] = e;
count[pick]++;
} else {
int best = 0;
for (int i = 1; i < n; i++) if (freeAt[i] < freeAt[best]) best = i;
freeAt[best] = freeAt[best] + (e - s);
count[best]++;
}
}
int ans = 0;
for (int i = 1; i < n; i++) if (count[i] > count[ans]) ans = i;
return ans;
}C++
int mostBooked(int n, vector<vector<int>>& meetings) {
vector<vector<int>> sorted = meetings;
sort(sorted.begin(), sorted.end(), [](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; });
vector<long long> freeAt(n, 0);
vector<int> count(n, 0);
for (auto& mt : sorted) {
long long s = mt[0], e = mt[1];
int pick = -1;
for (int i = 0; i < n; i++) {
if (freeAt[i] <= s) { pick = i; break; }
}
if (pick >= 0) {
freeAt[pick] = e;
count[pick]++;
} else {
int best = 0;
for (int i = 1; i < n; i++) if (freeAt[i] < freeAt[best]) best = i;
freeAt[best] = freeAt[best] + (e - s);
count[best]++;
}
}
int ans = 0;
for (int i = 1; i < n; i++) if (count[i] > count[ans]) ans = i;
return ans;
}JavaScript
var mostBooked = function(n, meetings) {
var sorted = meetings.slice();
sorted.sort(function(a, b) { return a[0] - b[0]; });
var freeAt = [], count = [], i;
for (i = 0; i < n; i++) { freeAt.push(0); count.push(0); }
for (var t = 0; t < sorted.length; t++) {
var s = sorted[t][0], e = sorted[t][1];
var pick = -1;
for (i = 0; i < n; i++) {
if (freeAt[i] <= s) { pick = i; break; }
}
if (pick >= 0) {
freeAt[pick] = e;
count[pick]++;
} else {
var best = 0;
for (i = 1; i < n; i++) if (freeAt[i] < freeAt[best]) best = i;
freeAt[best] = freeAt[best] + (e - s);
count[best]++;
}
}
var ans = 0;
for (i = 1; i < n; i++) if (count[i] > count[ans]) ans = i;
return ans;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms