Meeting Rooms III

Updated on 09 June, 2025
Meeting Rooms III header image

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

  • C++
  • Java
  • Python
cpp
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.

java
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.

python
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.

Comments

No comments yet.