Meeting Rooms III
Asked at Apple, Uber
Problem
Given n rooms and a list of meetings with start and end times, find the room that hosted the most meetings. If a room is free, assign to the lowest-numbered room. If none are free, the meeting is skipped. This tests your ability to simulate a scheduling system with a heap and hash map.
Asked At
| Company | Difficulty | |
|---|---|---|
| Apple | Hard | View all Apple questions → |
| Uber | Hard | View all Uber questions → |
How to Think About It
Key insight: sort meetings by start time, then simulate. Use a min-heap to track when each room becomes free (end_time, room_number). Use a second min-heap for available rooms (room numbers).
Visual walkthrough for n=2, meetings = [[0,5],[1,2],[5,10],[2,3]]:
- Sort: [[0,5],[1,2],[2,3],[5,10]]
- available = [0,1] (both rooms free)
- busy = []
- count = [0,0]
- [0,5]: room 0 available. Pop from available. count=[1,0]. Push (5,0) to busy. - [1,2]: room 1 available. Pop from available. count=[1,1]. Push (2,1) to busy.
- [2,3]: busy has (2,1). 2 <= 2, so room 1 is free. Pop (2,1). Room 0 busy until 5. Room 1 free. Push (3,1). count=[1,2]. - [5,10]: busy has (5,0) and (3,1). Pop (3,1). Room 1 free. Pop (5,0). Room 0 free. Push (10,1). count=[2,2]. Tie broken by room number. Room 0 wins.
Why two heaps: the "available rooms" heap ensures you always assign the lowest-numbered free room. The "busy rooms" heap (end_time, room_number) efficiently tells you when the next room becomes free.
When all rooms are busy and a meeting starts: the meeting is skipped. No room is assigned. The hash map or array tracking counts is not updated.
Edge case: multiple meetings ending at the same time as the current meeting's start. All those rooms are considered free. Pop all from the busy heap whose end_time <= current start, then pop the lowest available room.
Complexity: sort meetings O(m log m). Each meeting is pushed/popped from heaps at most once. Total: O(m log m + m log n) where m = number of meetings, n = number of rooms.
Optimal Approach
Sort meetings by start time. Maintain a min-heap busy of (end_time, room_number) and a min-heap available of room numbers. Initialize available with all room numbers 0 to n-1. Maintain a count array.
For each meeting (start, end):
- Pop all rooms from
busywhere end_time <= start (they are now free). Push their room numbers intoavailable. - If
availableis not empty: pop the smallest room number. Increment its count. Push (end, room) intobusy. - If
availableis empty: meeting is skipped.
After processing all meetings, find the room with the highest count. If there's a tie, return the lowest room number.
Time: O(m log m) for sorting + O(m log n) for heap operations. Space: O(m + n) for heaps and count array.
What Trips People Up in Real Interviews
Forgetting that when no room is free, the meeting duration is added to the earliest-ending meeting's end time. Don't skip the meeting — extend the busy room's end time by (end - start).
Sorting meetings by start time only, not by end time. You must process meetings in start-time order to simulate real scheduling. Sorting by end time breaks the simulation logic.
Assigning the lowest-numbered room incorrectly. Without the available heap, you might iterate rooms 0 to n-1 each time, making it O(n*m). The min-heap gives O(log n) assignment.
Forgetting that the tie-breaking rule is lowest room number, not first available. If two rooms become free at the same time, always pick the one with the smaller index.
Not popping all expired busy rooms before assigning. When a meeting starts at time t, ALL rooms with end_time <= t are free. You must pop them all before checking availability, not just one.
Solution Code
import heapq
def mostBooked(n, meetings):
meetings.sort()
available = list(range(n))
heapq.heapify(available)
busy = []
count = [0] * n
for start, end in meetings:
while busy and busy[0][0] <= start:
_, room = heapq.heappop(busy)
heapq.heappush(available, room)
if available:
room = heapq.heappop(available)
count[room] += 1
heapq.heappush(busy, (end, room))
else:
busy_end, room = heapq.heappop(busy)
count[room] += 1
heapq.heappush(busy, (busy_end + (end - start), room))
max_count = max(count)
for i in range(n):
if count[i] == max_count:
return iFrequently Asked Questions
What is the Meeting Rooms III problem?
Given `n` rooms and a list of meetings with start and end times, find the room that hosted the most meetings. If a room is free, assign to the lowest-numbered room. If none are free, the meeting is skipped. This tests your ability to simulate a scheduling system with a `heap` and `hash map`.
How do you solve Meeting Rooms III?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Meeting Rooms III?
Meeting Rooms III is asked at Apple, Uber. It is a hard difficulty problem.
What are common mistakes on Meeting Rooms III?
- Forgetting that when no room is free, the meeting duration is added to the earliest-ending meeting's end time. Don't skip the meeting — extend the busy room's end time by `(end - start)`.
- Sorting meetings by start time only, not by end time. You must process meetings in start-time order to simulate real scheduling. Sorting by end time breaks the simulation logic.
- Assigning the lowest-numbered room incorrectly. Without the `available` heap, you might iterate rooms 0 to n-1 each time, making it `O(n*m)`. The min-heap gives `O(log n)` assignment.
- Forgetting that the tie-breaking rule is lowest room number, not first available. If two rooms become free at the same time, always pick the one with the smaller index.
- Not popping all expired busy rooms before assigning. When a meeting starts at time t, ALL rooms with end_time <= t are free. You must pop them all before checking availability, not just one.