2402. Meeting Rooms III - Detailed Explanation

Problem Statement

In the "Meeting Rooms III" problem, you are given an integer n representing the number of meeting rooms (numbered from 0 to n - 1) and an array of meeting requests where each meeting is represented as [start, end]. Each meeting has a fixed duration (end − start). Meetings are scheduled in one of the available rooms according to the following rules:

• If there is a free meeting room at the meeting’s start time, assign the meeting to the room with the smallest room number.

• If no room is available at the meeting’s start time, choose the room that becomes available the earliest. In this case, the meeting is delayed until that room is free; its new start time becomes the room’s available time, and its end time is shifted by the same delay (i.e. the meeting duration stays the same).

Your task is to determine which room holds the most meetings after all meeting requests are processed. If there is a tie, return the room with the smallest number.

Hints

1. Sorting Meetings:
   Sort the meetings by their start times. This ensures that you process the meeting requests in the order they arrive.

2. Using Two Priority Queues:
   Use one min-heap (priority queue) for free rooms sorted by room number and another for busy rooms sorted by the time they become free (if two rooms free up at the same time, the room with the smaller number should come first).

3. Handling Delays:
   When no room is free at a meeting’s start time, pick the busy room that becomes available the earliest. The meeting will then start at that room’s available time, and its end time will be delayed by the duration of the meeting.

4. Counting Meetings:
   Maintain a counter for each room to track the number of meetings held. Update the count every time a meeting is assigned to a room.

Approaches

Simulation Using Priority Queues

• Step 1:
  Sort the list of meetings by their start time.

• Step 2:
  Initialize two priority queues:
  • Free Rooms: Contains all room numbers from 0 to n − 1 (min-heap based on room number).
  • Busy Rooms: Contains tuples (end_time, room_number) indicating when a room becomes free.

• Step 3:
  For each meeting request, first check the busy queue to free up any room whose meeting has ended by the current meeting's start time. Then, if a free room is available, assign the meeting to the free room with the smallest number. Otherwise, pick the busy room that becomes free the earliest, delay the meeting to that room’s available time, and update the meeting’s end time accordingly.

• Step 4:
  Increase the meeting count for the room that gets assigned the meeting.

• Step 5:
  After processing all meetings, identify the room with the highest meeting count (if there’s a tie, choose the room with the smallest number).

Complexity Analysis

• Time Complexity:
  Sorting the meetings takes O(m log m), where m is the number of meetings. Each meeting is processed with heap operations that take O(log n). Thus, the overall time complexity is O(m log m + m log n).

• Space Complexity:
  The space required is O(n + m) for storing the free rooms, busy rooms, and the meeting list.

Python Code

Java Code