HardArrayHash TableSortingHeapSimulationUpdated Sep 2026

2402. Meeting Rooms III

Asked at Apple, Uber

Difficulty

Hard

Time

O(m log m + m log n)

Space

O(m + n)

Pattern

Array

Companies

2

Problem

You are given n rooms, numbered 0 to n-1, and a list of meetings. Each meeting is a pair [start, end] and wants to run during the half-open time range [start, end) — it includes start but not end.

Process the meetings in order of their start time. For each meeting, assign it to the free room with the smallest number. A room is free at time start if its previous meeting ended at or before start. If every room is busy, the meeting does not get skipped — it is delayed until the earliest time any room becomes free, and it keeps its original length (end - start). If several rooms become free at the same moment, the meeting with the earliest original start time gets the room first.

Return the number of the room that hosted the most meetings. If two or more rooms tie, return the smallest room number.

Two rooms, four meetings

meetings[0,10][1,5][2,7][3,4]0123The first two meetings fit into rooms 0 and 1 rightaway.meetings[0,10][1,5][2,7][3,4]0123Meetings [2,7] and [3,4] arrive while both rooms arebusy, so they are delayed.
Rooms 0 and 1 fill up fast, so later meetings must wait for a room to free up.

Constraints

  • ●1 <= n <= 100
  • ●1 <= meetings.length <= 10^5
  • ●meetings[i].length == 2
  • ●0 <= starti < endi <= 5 * 10^5
  • ●All values of starti are unique

Examples

Example 1
Inputn = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
Output0
WhyMeeting [0,10] takes room 0 and [1,5] takes room 1. Now both rooms are busy, so [2,7] waits until room 1 frees at time 5 and runs [5,10). Then [3,4] waits until time 10 and runs [10,11) in room 0. Each room hosted 2 meetings, so the tie goes to room 0.
Example 2
Inputn = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
Output1
WhyThe first three meetings fill rooms 0, 1 and 2. Meeting [4,9] waits for room 2 (free at 5) and runs [5,10). Meeting [6,8] waits until time 10, when rooms 1 and 2 both free up; room 1 has the earlier original start time, so it gets room 1 and runs [10,12). Room 0 hosted 1 meeting, rooms 1 and 2 hoste

Asked At

2 companies
CompanyDifficulty
AppleHardView all Apple questions →
UberHardView all Uber questions →

How to Think About It

1

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).

2

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.

3

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.

4

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.

5

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):

  1. Pop all rooms from busy where end_time <= start (they are now free). Push their room numbers into available.
  2. If available is not empty: pop the smallest room number. Increment its count. Push (end, room) into busy.
  3. If available is 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.

Two heaps drive the simulation

available01frontbackStart: both rooms are free, smallest number on top.busy (end, room)(5,1)(10,0)← topAfter [0,10] and [1,5]: room 1 frees at 5, room 0 at10.busy (end, room)(10,1)(11,0)← topMeeting [2,7] waits for room 1 and runs [5,10);meeting [3,4] waits for room 0 and runs [10,11).if available: room = pop(available)else: end, room = pop(busy); end += lengthcount[room] += 1
The available heap gives the smallest free room; the busy heap gives the next room to free up.
ComplexityTime O(m log m + m log n)Space O(m + n)Sorting the meetings costs O(m log m); each meeting is pushed and popped from the heaps at most once, costing O(m log n), and we store the busy heap plus the count array.

What Trips People Up in Real Interviews

1

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).

2

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.

3

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.

4

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.

5

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

O(m log m + m log n) time
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 i

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(m log m + m log n) time and O(m + n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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.