Meeting Rooms III

How it works

We can simplify to a single heap that tracks (end_time, room). Initially all rooms have end time 0. Before assigning a meeting, we update any rooms whose end time is before the meeting's start to have end time equal to the start (they become available). Then we pop the room with the smallest end time (and smallest room number on ties), assign the meeting, and push the room back with the new end time.

Steps

1. Sort meetings by start time.
2. Initialize a min-heap available with (0, room) for each room 0 to n - 1.
3. Initialize an array count of size n.
4. For each (start, end):
   • While available[0].end_time < start, pop (_, room) and push (start, room).
   • Pop (end_time, room) from the heap.
   • Push (end_time + (end - start), room) back to the heap.
   • Increment count[room].
5. Return the index with maximum count.

Complexity

• Time complexity:
  • O(m log m + m log n) time in average case.
  • O(m log m + m * n) time in worst case.
• Space complexity: O(n)

Where n is the number of rooms and m is the number of meetings.

Things to watch for

Forgetting to Sort Meetings by Start Time

Meetings must be processed in chronological order. Without sorting, you cannot correctly determine which room becomes available first or when meetings need to be delayed.

Integer Overflow When Calculating Delayed End Times

When meetings are delayed, end times can grow very large. Using int instead of long can cause overflow. Always use long or equivalent 64-bit integer types for end times.

Incorrect Tie-Breaking for Room Selection

When multiple rooms are available, you must choose the room with the smallest index. When multiple rooms become free at the same time, you must also prefer the smaller index. Failing to implement this tie-breaking correctly leads to wrong answers.

Not Preserving Meeting Duration When Delaying

When a meeting is delayed because no room is available, the meeting duration must remain the same. The new end time should be earliest_available_time + (original_end - original_start), not simply the original end time.

Confusing Available vs Used Room Logic with Two Heaps

When using two heaps, it is easy to forget to move rooms from the used heap back to the available heap when their meetings end. Always check and transfer rooms whose end time is at or before the current meeting's start time before attempting to assign a room.

from typing import List
import heapq

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        meetings.sort()
        available = []
        count = [0] * n

        for i in range(n):
            heapq.heappush(available, (0, i))

        for start, end in meetings:
            while available and available[0][0] < start:
                end_time, room = heapq.heappop(available)
                heapq.heappush(available, (start, room))

            end_time, room = heapq.heappop(available)
            heapq.heappush(available, (end_time + (end - start), room))
            count[room] += 1

        return count.index(max(count))

class Solution {
public:
    int mostBooked(int n, vector<vector<int>>& meetings) {
        sort(meetings.begin(), meetings.end());
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> available;
        for (int i = 0; i < n; i++) {
            available.push({0, i});
        }
        vector<int> count(n);

        for (const auto& meeting : meetings) {
            int start = meeting[0], end = meeting[1];
            while (!available.empty() && available.top().first < start) {
                auto [end_time, room] = available.top();
                available.pop();
                available.push({start, room});
            }

            auto [end_time, room] = available.top();
            available.pop();
            available.push({end_time + (end - start), room});
            count[room]++;
        }

        return max_element(count.begin(), count.end()) - count.begin();
    }
};