Meeting Rooms III

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;
    }
};

This solution in C++ is designed to determine the room used most frequently in a schedule of meetings.

• Start by initializing usageCount to track the number of times each room is used, and two priority queues: bookedRooms for managing rooms that are currently booked and their release times, and freeRooms for quickly finding the next available room.
• Populate freeRooms with all room indices available from 0 to totalRooms - 1.
• Sort the provided schedules by their start times to process them in order.
• Iterate over each interval in schedules. For each meeting:
  • Free up any rooms where the booked end time is less than or equal to the meeting's start time.
  • If a free room is available, book it for the current meeting and update the usage count.
  • If no rooms are free, adjust the end time of the currently booked meeting to accommodate the new meeting and update the usage count.
• At the end of processing all meetings, iterate through usageCount to find the room with the maximum usage.

Return the index of the room with the highest usage count. This index represents the room that has been used most frequently. The use of priority queues ensures that the rooms are managed and booked efficiently based on their availability and timings. This approach effectively handles overlapping meetings and optimizes room allocation.

class MeetingScheduler {
    public int roomMostBooked(int rooms, int[][] intervals) {
        var counts = new int[rooms];
        var busyRooms = new PriorityQueue<long[]>((a, b) -> a[0] != b[0] ? Long.compare(a[0], b[0]) : Long.compare(a[1], b[1]));
        var freeRooms = new PriorityQueue<Integer>();
    
        for (int i = 0; i < rooms; i++) {
            freeRooms.offer(i);
        }
    
        Arrays.sort(intervals, (a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
    
        for (int[] interval : intervals) {
            int start = interval[0], finish = interval[1];
    
            while (!busyRooms.isEmpty() && busyRooms.peek()[0] <= start) {
                int freeRoom = (int) busyRooms.poll()[1];
                freeRooms.offer(freeRoom);
            }
    
            if (!freeRooms.isEmpty()) {
                int freeRoom = freeRooms.poll();
                busyRooms.offer(new long[]{finish, freeRoom});
                counts[freeRoom]++;
            } else {
                long nextAvailable = busyRooms.peek()[0];
                int bookedRoom = (int) busyRooms.poll()[1];
                busyRooms.offer(new long[]{nextAvailable + finish - start, bookedRoom});
                counts[bookedRoom]++;
            }
        }
    
        int maximumBookings = 0, roomWithMaxBookings = 0;
        for (int i = 0; i < rooms; i++) {
            if (counts[i] > maximumBookings) {
                maximumBookings = counts[i];
                roomWithMaxBookings = i;
            }
        }
    
        return roomWithMaxBookings;
    }
}

This Java implementation addresses the problem of scheduling meetings in available rooms while keeping track of the room usage frequency. It determines which room gets booked the most. To achieve this, the following steps are implemented:

1. Initialize arrays to keep count of each room's bookings.
2. Use two priority queues, one (busyRooms) to keep track of rooms that are currently occupied sorted by their release time and another (freeRooms) that maintains a list of free rooms sorted by room number.
3. Start by filling the freeRooms queue with all available rooms.
4. Sort the meetings based on their start time to ensure meetings are processed in the order they begin.
5. Iterate through each interval, checking and updating the state of each room:
   • As each meeting's start time comes up, check the busyRooms queue to free up rooms that are no longer in use.
   • If rooms are available in freeRooms, assign the room, mark it as busy for the duration of the meeting, and increment its booking count.
   • If no rooms are available, wait until the next room is freed, and then adjust the booking time accordingly, extending the current meeting's duration to a later time. The booking count for this room is also incremented.
6. After processing all intervals, identify the room with the highest booking count.

The solution uses efficient data structures to handle varying meeting times and room assignments dynamically. It optimally determines which room is the most frequently used, handling cases where all rooms might be continuously occupied by adjusting the schedule to accommodate all meetings.

By the end of this implementation, you retrieve the room that is most frequently booked, based on the given meeting times and the total number of available rooms.

class RoomScheduler:
    def busiestRoom(self, total_rooms: int, appointment_times: List[List[int]]) -> int:
        free_rooms, active_rooms = list(range(total_rooms)), []
        heapify(free_rooms)
        appointments_counter = [0] * total_rooms
        for arrival, departure in sorted(appointment_times):
            while active_rooms and active_rooms[0][0] <= arrival:
                _, room_number = heappop(active_rooms)
                heappush(free_rooms, room_number)
            if free_rooms:
                room_number = heappop(free_rooms)
                heappush(active_rooms, [departure, room_number])
            else:
                room_release_time, room_number = heappop(active_rooms)
                heappush(
                    active_rooms,
                    [room_release_time + departure - arrival, room_number]
                )
            appointments_counter[room_number] += 1
        return appointments_counter.index(max(appointments_counter))

The provided Python solution focuses on determining the busiest meeting room by analyzing a series of appointment start and end times for multiple rooms. Here's how the solution works:

1. Define the RoomScheduler class with the busiestRoom method that takes the total number of meeting rooms and a list of appointment times as inputs.

2. Utilize two lists, free_rooms to track available rooms and active_rooms to manage rooms that are currently in use. The rooms in free_rooms are maintained in a heap structure to ensure the quickest access to the next available room.

3. Create an appointments_counter list initialized to zero, which will count the number of appointments for each room.

4. Process each appointment, sorted by their start times. For each appointment:

   • Release rooms that have completed their current meetings by checking if the end times are less than or equal to the current appointment's start time.
   • Assign the current appointment to a room. If no free rooms are available, adjust the meeting time of a room which will release soonest by extending its end time.
   • Update the appointment count for the utilized room.

5. At the end of all appointments, the function returns the index (representing the room number) of the maximum value in appointments_counter, which indicates the busiest room based on the number of appointments held.

This solution effectively manages and schedules multiple rooms for various time-slotted events, ensuring optimal usage and tracking of room occupancy. It leverages heap data structures to manage room states efficiently, which is critical for performance in scenarios with many rooms and appointments.