Meeting Rooms III

Problem Description

You are given an integer n. There are n rooms numbered from 0 to n - 1.

You are given a 2D integer array meetings where meetings[i] = [starti, endi] means that a meeting will be held during the half-open interval [starti, endi). All start times are distinct.

Meetings are allocated to rooms in the following manner:

1. Each meeting will take place in the unused room with the lowest number.
2. If there are no available rooms, the meeting will be delayed until a room becomes free. The delayed meeting should have the same duration as the original meeting.
3. When a room becomes unused, meetings that have been delayed should be given the room in the order of their original start times.

Return the number of the room that held the most meetings. If there are multiple rooms, return the room with the lowest number.

Examples

Constraints

• 1 ≤ n ≤ 100
• 1 ≤ meetings.length ≤ 10⁵
• meetings[i].length == 2
• 0 ≤ starti < endi ≤ 5 * 10⁵
• All starti are distinct

Two Heaps: Available Rooms and Ongoing Meetings

Sort all meetings by their original start time. We need to allocate each meeting to the lowest-indexed free room.

We track rooms using two min-heaps:

1. freeRooms: a min-heap containing room indices (0 to n - 1).
2. busyRooms: a min-heap containing ongoing meetings, stored as [endTime, roomNumber], sorted by endTime (ties broken by roomNumber).

For each meeting [start, end]:

1. Free all rooms whose meetings finished before or at start. Move these room numbers from busyRooms back to freeRooms.
2. Case A (Free room available): pop the lowest-indexed room from freeRooms. Schedule the meeting there: push [end, room] to busyRooms.
3. Case B (No free room): the meeting must be delayed. Pop the earliest-finishing meeting from busyRooms (say, it finishes at earliestFreeTime). The delayed meeting will start at earliestFreeTime and run for duration = end - start. Push [earliestFreeTime + duration, room] back to busyRooms.
4. Keep track of how many times each room index is used.

Solution: Two Heaps Simulation

import java.util.*;

class Solution {
    public int mostBooked(int n, int[][] meetings) {
        Arrays.sort(meetings, (a, b) -> Integer.compare(a[0], b[0]));

        PriorityQueue<Integer> freeRooms = new PriorityQueue<>();
        for (int i = 0; i < n; i++) freeRooms.offer(i);

        // busyRooms: [endTime, roomNumber]
        PriorityQueue<long[]> busyRooms = new PriorityQueue<>(
            (a, b) -> a[0] != b[0] ? Long.compare(a[0], b[0]) : Long.compare(a[1], b[1])
        );

        int[] count = new int[n];

        for (int[] meeting : meetings) {
            long start = meeting[0], end = meeting[1];

            // free up rooms that are done by current start time
            while (!busyRooms.isEmpty() && busyRooms.peek()[0] <= start) {
                freeRooms.offer((int) busyRooms.poll()[1]);
            }

            if (!freeRooms.isEmpty()) {
                int room = freeRooms.poll();
                count[room]++;
                busyRooms.offer(new long[]{end, room});
            } else {
                long[] top = busyRooms.poll();
                long earliestFree = top[0];
                int room = (int) top[1];
                count[room]++;
                busyRooms.offer(new long[]{earliestFree + (end - start), room});
            }
        }

        int maxIdx = 0;
        for (int i = 1; i < n; i++) {
            if (count[i] > count[maxIdx]) maxIdx = i;
        }
        return maxIdx;
    }
}

import heapq

class Solution:
    def mostBooked(self, n: int, meetings: list[list[int]]) -> int:
        meetings.sort()

        free_rooms = list(range(n))
        heapq.heapify(free_rooms)

        busy_rooms = []  # (end_time, room_number)
        count = [0] * n

        for start, end in meetings:
            # release all rooms finished by current start time
            while busy_rooms and busy_rooms[0][0] <= start:
                end_time, room = heapq.heappop(busy_rooms)
                heapq.heappush(free_rooms, room)

            if free_rooms:
                room = heapq.heappop(free_rooms)
                count[room] += 1
                heapq.heappush(busy_rooms, (end, room))
            else:
                earliest_free, room = heapq.heappop(busy_rooms)
                duration = end - start
                count[room] += 1
                heapq.heappush(busy_rooms, (earliest_free + duration, room))

        max_val = -1
        ans = -1
        for i, v in enumerate(count):
            if v > max_val:
                max_val = v
                ans = i
        return ans

#include <vector>
#include <queue>
#include <algorithm>

class Solution {
public:
    int mostBooked(int n, std::vector<std::vector<int>>& meetings) {
        std::sort(meetings.begin(), meetings.end());

        std::priority_queue<int, std::vector<int>, std::greater<int>> freeRooms;
        for (int i = 0; i < n; i++) freeRooms.push(i);

        // min-heap: {endTime, roomNumber}
        using T = std::pair<long long, int>;
        std::priority_queue<T, std::vector<T>, std::greater<T>> busyRooms;

        std::vector<int> count(n, 0);

        for (const auto& meeting : meetings) {
            long long start = meeting[0], end = meeting[1];

            while (!busyRooms.empty() && busyRooms.top().first <= start) {
                freeRooms.push(busyRooms.top().second);
                busyRooms.pop();
            }

            if (!freeRooms.empty()) {
                int room = freeRooms.top(); freeRooms.pop();
                count[room]++;
                busyRooms.push({end, room});
            } else {
                auto [earliestFree, room] = busyRooms.top(); busyRooms.pop();
                count[room]++;
                busyRooms.push({earliestFree + (end - start), room});
            }
        }

        int maxIdx = 0;
        for (int i = 1; i < n; i++) {
            if (count[i] > count[maxIdx]) maxIdx = i;
        }
        return maxIdx;
    }
};

Complexity Analysis:

• Time Complexity: O(M log M + M log N) where M is the number of meetings and N is the number of rooms. Sorting meetings takes O(M log M). Each meeting triggers heap operations of cost O(log N).
• Space Complexity: O(N) to store room queues and allocation counts.

Where it breaks: when a meeting is delayed, its new end time is earliestFree + (end - start). Because start/end times can reach 5 * 10⁵, a series of delays can cause the time value to exceed 2³¹ - 1. You must use 64-bit integers (long in Java, long long in C++) for time variables to prevent overflow.

Common Mistakes

• Incorrect tie-breaker in busyRooms. If two meetings finish at the same time, the one in the lower-numbered room must be popped first to satisfy requirement 1. The custom comparator/tuple ordering handles this correctly.
• Using 32-bit integers for end times. Delays propagate, pushing the time scale past the 32-bit limit.

← All Problems