{x}
blog image

Meeting Rooms III

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-closed time interval [starti, endi). All the values of starti are unique.

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 an earlier original start time should be given the room.

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

A half-closed interval [a, b) is the interval between a and b including a and not including b.

 

Example 1:

Input: n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
Output: 0
Explanation:
- At time 0, both rooms are not being used. The first meeting starts in room 0.
- At time 1, only room 1 is not being used. The second meeting starts in room 1.
- At time 2, both rooms are being used. The third meeting is delayed.
- At time 3, both rooms are being used. The fourth meeting is delayed.
- At time 5, the meeting in room 1 finishes. The third meeting starts in room 1 for the time period [5,10).
- At time 10, the meetings in both rooms finish. The fourth meeting starts in room 0 for the time period [10,11).
Both rooms 0 and 1 held 2 meetings, so we return 0.

Example 2:

Input: n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
Output: 1
Explanation:
- At time 1, all three rooms are not being used. The first meeting starts in room 0.
- At time 2, rooms 1 and 2 are not being used. The second meeting starts in room 1.
- At time 3, only room 2 is not being used. The third meeting starts in room 2.
- At time 4, all three rooms are being used. The fourth meeting is delayed.
- At time 5, the meeting in room 2 finishes. The fourth meeting starts in room 2 for the time period [5,10).
- At time 6, all three rooms are being used. The fifth meeting is delayed.
- At time 10, the meetings in rooms 1 and 2 finish. The fifth meeting starts in room 1 for the time period [10,12).
Room 0 held 1 meeting while rooms 1 and 2 each held 2 meetings, so we return 1.

 

Constraints:

  • 1 <= n <= 100
  • 1 <= meetings.length <= 105
  • meetings[i].length == 2
  • 0 <= starti < endi <= 5 * 105
  • All the values of starti are unique.

Solution Explanation: Meeting Rooms III

This problem involves assigning meetings to rooms, considering room availability and prioritizing meetings based on their original start times. The optimal approach uses priority queues (min-heaps) for efficient management of available rooms and ongoing meetings.

Algorithm:

  1. Initialization:

    • Sort the meetings array by start time. This ensures we process meetings in chronological order.
    • Create a min-heap idle to store the indices of available rooms. Initially, all rooms (0 to n-1) are available.
    • Create a min-heap busy to store the ongoing meetings. The heap is ordered by the end time of the meeting, then by room index (to handle ties). Each element in busy is a pair (end_time, room_index).
    • Initialize a cnt array to track the number of meetings held in each room.

  2. Meeting Assignment:

    • Iterate through the sorted meetings array:
      • Check for available rooms: While there are busy rooms ending before the current meeting's start time, move those rooms from busy to idle.
      • Assign to an idle room: If there are idle rooms, pop the room with the lowest index from idle, assign the meeting to that room, increment cnt for that room, and add the meeting's end time and room index to busy.
      • Delay and assign: If no idle rooms are available, the meeting is delayed. Take the meeting with the earliest end time (and lowest room index) from busy. Calculate the new end time (original end time + delay) and add the updated meeting to busy. Increment cnt for that room.

  3. Result:

    • After processing all meetings, find the room with the maximum number of meetings (max(cnt)). Return the index of the first room with this maximum count.

Time Complexity Analysis:

  • Sorting meetings: O(m log m), where m is the number of meetings.
  • Heap operations (push, pop): Each meeting involves at most O(log n) operations for idle and O(log m) operations for busy. Since we iterate through all 'm' meetings, this part becomes O(m log m).
  • Overall time complexity: O(m log m) + O(m log m) = O(m log m). The sorting dominates the time complexity.

Space Complexity Analysis:

  • idle and busy heaps: O(n) and O(m) respectively in the worst case.
  • cnt array: O(n)
  • Overall space complexity: O(m + n).

Code Examples (Python, Java, C++, Go):

The code examples in the original response accurately reflect the algorithm described above. The use of priority queues in each language makes for an efficient and clear solution. The Go code also cleverly uses custom heap structures. All the provided code snippets have the same time and space complexity.