Meeting Rooms III

Problem Statement

In this problem, you are managing a set of rooms where meetings are scheduled based on their start and end times provided in a 2D integer array meetings. Each sub-array [starti, endi] represents a meeting scheduled during a half-closed interval [starti, endi), meaning the meeting starts at starti and ends right before endi. All meeting start times (starti) are unique. The objective is to assign these meetings to n available rooms (numbered from 0 to n-1) using a specific set of rules:

1. Preferentially fill the lowest numbered unused room with a new meeting.
2. If no rooms are currently available, delay the meeting until one is freed.
3. When a room becomes available, assign it to the delayed meeting that originally had the earliest start time.

The challenge lies in efficiently determining the room that has accommodated the most meetings by the end of all schedules. If multiple rooms share the maximum count, the room with the smallest number should be returned. This scenario simulates a common resource allocation problem with constraints based on availability and priority.

Examples

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.

Approach and Intuition

Given the constraints and problem setup, an effective approach would involve keeping track of room availability and the number of meetings each room has held. Here's how one might think about structuring the solution:

1. Initialize Room States:

   • Maintain an array endtimes to track when each of the n rooms will be free.
   • Use room_meeting_count array to keep track of how many meetings each room has held.

2. Sort Meetings:

   • Sort meetings array by start times. This ensures that you allocate rooms to meetings in the order they are meant to begin.

3. Allocate Rooms:

   • For each meeting, check room availabilities:
     • If a room is available (current time is greater than or equal to room's end time in endtimes), assign the meeting.
     • Update the endtimes based on the current meeting's end time.
     • Increment that room's count in room_meeting_count.
   • If no rooms are available at the time of a meeting's start, delay the meeting:
     • Keep track of the meetings being delayed using a priority queue or another suitable data structure to properly manage delayed meetings based on their original start times.

4. Find Most Used Room:

   • After processing all meetings, identify the room with the maximum count in room_meeting_count.
   • If there's a tie, the smallest numbered room is selected as per the given rules.

This method is efficient given the constraints, as sorting the meetings and iterating through them provides a linearithmic solution, and with room and meeting count management only taking linear time and space respective to the number of rooms or meetings.

Solutions

class Solution {
public:
    int mostFrequentRoom(int totalRooms, vector<vector<int>>& schedules) {
        vector<int> usageCount(totalRooms, 0);
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> bookedRooms;
        priority_queue<int, vector<int>, greater<int>> freeRooms;
        for (int roomNum = 0; roomNum < totalRooms; roomNum++) {
            freeRooms.push(roomNum);
        }
        sort(schedules.begin(), schedules.end());
    
        for (const auto& interval : schedules) {
            int startTime = interval[0], endTime = interval[1];
    
            while (!bookedRooms.empty() && bookedRooms.top().first <= startTime) {
                int availableRoom = bookedRooms.top().second;
                bookedRooms.pop();
                freeRooms.push(availableRoom);
            }
            if (!freeRooms.empty()) {
                int nextRoom = freeRooms.top();
                freeRooms.pop();
                bookedRooms.push({endTime, nextRoom});
                usageCount[nextRoom]++;
            } else {
                auto [nextAvailableTime, activeRoom] = bookedRooms.top();
                bookedRooms.pop();
                bookedRooms.push({nextAvailableTime + endTime - startTime, activeRoom});
                usageCount[activeRoom]++;
            }
        }
    
        int maximumUsage = 0, roomWithMaxUsage = 0;
        for (int roomIdx = 0; roomIdx < totalRooms; roomIdx++) {
            if (usageCount[roomIdx] > maximumUsage) {
                maximumUsage = usageCount[roomIdx];
                roomWithMaxUsage = roomIdx;
            }
        }
        return roomWithMaxUsage;
    }
};