Generated by Codex with GPT-5

Quick facts

• Difficulty: HARD
• Problem: Meeting Rooms III
• Main tags: Array, Sorting, Heap (Priority Queue), Simulation
• Frequency in source list: 17.6

What the problem is really asking

This is not the classic “how many meeting rooms are needed?” question.

The number of rooms is fixed up front, and every meeting has to be assigned under three rules:

1. Meetings are considered in increasing order of their original start time.
2. If one or more rooms are free, the meeting must use the smallest room number.
3. If no room is free, the meeting waits until the earliest room becomes free, keeps the same duration, and still uses the smallest room number among rooms that become free at that earliest time.

After all of that scheduling is done, the real output is the room that hosted the most meetings. If multiple rooms tie, the answer is the smallest room number.

So the hard part is not overlap detection by itself. The hard part is simulating the scheduling rules exactly, including delays and tie-breaking, without slowing down to an expensive room-by-room scan for every meeting.

Why the obvious simulation is too slow

A direct simulation would sort the meetings by start time and, for each one, scan every room to answer two questions:

• Is there a free room right now?
• If not, which room becomes free first?

That works, but it costs O(n) per meeting when there are n rooms. With many meetings, repeated full scans become the bottleneck.

The problem becomes much easier once those two questions are separated, because they are really different lookup tasks:

• among free rooms, find the smallest room number
• among busy rooms, find the earliest finishing room, breaking ties by room number

Each of those tasks maps naturally to its own min-heap.

The key insight: use two heaps for two different priorities

Maintain these two structures while processing meetings in sorted start-time order:

• available_rooms: a min-heap of free room numbers
• busy_rooms: a min-heap of (end_time, room_number) pairs

For each meeting [start, end):

First, release every room whose current meeting ends on or before start. Those rooms move from busy_rooms back into available_rooms.

If at least one room is now free, pop the smallest room number and schedule the meeting at its original time.

If no room is free, pop the room with the earliest end time from busy_rooms. That is the room this meeting must wait for. The meeting is then delayed to start at that end time, and its new end time becomes:

earliest_end_time + (end - start)

In both cases, increment that room’s usage count and push its new (actual_end_time, room_number) back into busy_rooms.

That is the whole algorithm.

A concrete example

Take n = 2 rooms and meetings:

[[0, 10], [1, 5], [2, 7], [3, 4]]

Process them in start-time order:

• [0, 10] goes to room 0
• [1, 5] goes to room 1
• [2, 7] finds both rooms busy, so it waits for the earliest room to free up
• room 1 frees at time 5, so [2, 7] becomes [5, 10] in room 1
• [3, 4] also finds both rooms busy; now the earliest free time is 10
• both rooms become free at 10, so the smaller room number, 0, is chosen
• [3, 4] becomes [10, 11] in room 0

That example shows both tricky parts:

• delayed meetings keep their original duration
• tie-breaking is always done by room number

How to derive this in an interview

The cleanest path is:

1. Start with the sorted-by-start-time simulation.
2. Notice the repeated work is finding the right room quickly.
3. Split that into the two queries the algorithm really needs.
4. Use one min-heap for free rooms and one min-heap for busy rooms.
5. Explain why the busy-room heap must be ordered by (end_time, room_number) so delayed meetings respect both scheduling rules.

That derivation is better than just saying “use two heaps,” because it shows exactly why each heap exists.

Python solution

from heapq import heapify, heappop, heappush
from typing import List, Tuple


Meeting = Tuple[int, int]
BusyRoom = Tuple[int, int]  # (next_free_time, room_number)


class MeetingRoomScheduler:
    """Simulate the room assignment rules for Meeting Rooms III."""

    def __init__(self, room_count: int) -> None:
        self.available_rooms: List[int] = list(range(room_count))
        heapify(self.available_rooms)

        self.busy_rooms: List[BusyRoom] = []
        self.meeting_counts: List[int] = [0] * room_count

    def most_booked_room(self, meetings: List[Meeting]) -> int:
        for start_time, end_time in sorted(meetings, key=lambda meeting: meeting[0]):
            self._release_finished_rooms(current_time=start_time)
            assigned_room, actual_end_time = self._assign_room(
                start_time=start_time,
                end_time=end_time,
            )

            self.meeting_counts[assigned_room] += 1
            heappush(self.busy_rooms, (actual_end_time, assigned_room))

        return self._room_with_highest_meeting_count()

    def _release_finished_rooms(self, current_time: int) -> None:
        """
        Move every room that has finished by current_time back into the pool of
        available rooms.
        """
        while self.busy_rooms and self.busy_rooms[0][0] <= current_time:
            _, room_number = heappop(self.busy_rooms)
            heappush(self.available_rooms, room_number)

    def _assign_room(self, start_time: int, end_time: int) -> BusyRoom:
        """
        Return (room_number, actual_end_time) for the current meeting.

        If a room is already free, use the smallest room number immediately.
        Otherwise, delay the meeting until the earliest room becomes free while
        preserving the meeting's duration.
        """
        duration = end_time - start_time

        if self.available_rooms:
            room_number = heappop(self.available_rooms)
            return room_number, end_time

        earliest_free_time, room_number = heappop(self.busy_rooms)
        delayed_end_time = earliest_free_time + duration
        return room_number, delayed_end_time

    def _room_with_highest_meeting_count(self) -> int:
        """
        Return the room with the most meetings. Because the scan goes from low
        to high room number and only updates on a strict improvement, ties keep
        the smaller room number automatically.
        """
        best_room = 0

        for room_number in range(1, len(self.meeting_counts)):
            if self.meeting_counts[room_number] > self.meeting_counts[best_room]:
                best_room = room_number

        return best_room


class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        scheduler = MeetingRoomScheduler(room_count=n)
        normalized_meetings = [(start, end) for start, end in meetings]
        return scheduler.most_booked_room(normalized_meetings)

Why this works

The two heaps maintain exactly the information the scheduling rules ask for.

The available_rooms heap always contains every room that is free at the current meeting’s start time, ordered by room number. That makes choosing the smallest valid room immediate.

The busy_rooms heap always contains every occupied room, ordered first by the next time it becomes free and then by room number. That means when a meeting must wait, popping the top of this heap gives exactly the room the rules require: the earliest one to become available, with the smallest room number breaking ties.

Processing meetings in original start-time order is also essential. It guarantees that earlier meetings get priority when multiple future meetings are waiting, which is exactly what the problem statement wants. Since each meeting causes only a constant number of heap operations, the scheduling work is O(m log n) for m meetings and n rooms, after an initial O(m log m) sort. The extra space is O(n) for the heaps and count array.

Interview follow-ups

What if the interviewer wants the actual room assignment for every meeting, not just the busiest room?

The same simulation still works. The only change is that each meeting should carry its original index, and whenever a room is assigned, the algorithm stores that room number in a result array. If the interviewer also wants the delayed time range, the algorithm can store the actual start time and actual end time as well. Nothing about the heap logic changes, because the scheduling decision is identical. The complexity stays O(m log m + m log n) time with O(n + m) space once the per-meeting output is recorded.

Can this be done with one heap instead of two?

Not cleanly if both tie-breaking rules must stay efficient. One heap can tell which busy room frees earliest, but it cannot also tell which free room has the smallest room number unless free rooms are represented separately in sorted order. That is why the two-heap design is the right abstraction: one heap answers “who is free and has the smallest label?” and the other answers “who becomes free first?” Trying to force both jobs into one structure usually makes some operation degrade to a scan, which turns the simulation back toward O(mn) time.

What changes if meetings arrive online instead of all being given up front?

If meetings arrive in nondecreasing start-time order, almost nothing changes. The scheduler can keep the same two heaps as persistent state and process each new meeting in O(log n) time, because there is no need for the initial sort. That is a nice streaming variant. But if meetings can arrive out of chronological order, the original problem changes substantially. Inserting a meeting with an earlier start time can change the assignments of many later meetings, so the simple forward simulation is no longer enough. The tradeoff is between simplicity and flexibility: the offline sorted version is easy and optimal for the LeetCode problem, while out-of-order updates require much more complicated rescheduling logic.

Practical takeaway

The fastest way to see this problem clearly is to stop thinking in terms of intervals alone and start thinking in terms of scheduling decisions.

At every step, the algorithm needs exactly two answers: the smallest free room right now, or the earliest room that will become free next. Once those are turned into two min-heaps, the rest of the solution becomes a straightforward simulation.