2402. Meeting Rooms 3

Problem Statement in English

You’re given an integer n representing the number of meeting rooms available, and a 2D integer array meetings where $meetings[i] = [start_i, end_i]$ represents the start and end times of the ith meeting.

Your task is to determine which meeting room gets booked the most number of times after scheduling all the meetings.

The scheduling follows these rules:

1. Each meeting must be assigned to a room.
2. If a room is free at the start time of a meeting, the meeting is assigned to that room.
3. If multiple rooms are free, the meeting is assigned to the room with the lowest numerical ID.
4. If no rooms are free at the start time of a meeting, the meeting is delayed until the earliest room becomes free. The meeting is then assigned to that room.
5. The duration of the meeting remains the same, even if it is delayed.

Approach

To solve the problem of determining which meeting room gets booked the most number of times, we can use a min-heap (priority queue) to efficiently manage the available rooms and the ongoing meetings. We also need a dictionary to keep track of how many times each room has been booked.

We keep two heaps:

1. A min-heap for available rooms, initialized with all room IDs.
2. A min-heap for ongoing meetings, which will store tuples of $(\text{end time}, \text{room id})$.

When we use up a room for a meeting, we increment its booking count in the dictionary, remove it from the available rooms heap, and add it to the ongoing meetings heap with its end time.

When a meeting ends, we free up the room by removing it from the ongoing meetings heap and adding it back to the available rooms heap.

We then allocate a room for the next meeting.oca

Solution in Python

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        rooms = [i for i in range(n)]
        heapify(rooms)

        ledger = []
        stats = defaultdict(int)

        for meeting in sorted(meetings):
            start, end = meeting

            while ledger and ledger[0][0] <= start:
                _, room = heappop(ledger)
                heappush(rooms, room)

            if rooms:
                room = heappop(rooms)
                heappush(ledger, (end, room))
                stats[room] += 1
            else:
                p_end, room = heappop(ledger)
                duration = end - start
                heappush(ledger, (max(start, p_end) + duration, room))
                stats[room] += 1

        res = 0
        for k in range(n):
            if stats[k] > stats[res]:
                res = k

        return res

Complexity

• Time: $O(n \log n)$
  Since we sort the meetings which takes $O(n \log n)$ time and for each meeting we perform heap operations which take $O(\log n)$ time.

• Space: $O(n)$
  Since we use heaps to store the rooms and ledger which can take up to $O(n)$ space.

Mistakes I Made

I didn’t free rooms eagerly, and instead freed them only when needed. This caused incorrect room assignment for some meetings.

For example, if a room with a lower ID becomes free, and there are already other rooms available, we should assign the meeting to the one with the lower ID instead of an already free room that has a higher ID.

And we are done.