2402. Meeting Rooms III


Problem Description

In the given problem, we have n rooms where meetings are scheduled to take place. Our goal is to identify which room will have hosted the most number of meetings by the end of all meetings. Each meeting is represented as a pair of integers indicating its start and end times. A key point to note is that these meetings' start times are unique, meaning no two meetings will start at exactly the same time. The meetings follow certain allocation rules to rooms:

  1. Each meeting is scheduled in the lowest-numbered room available.
  2. If all rooms are busy, the meeting will be delayed until a room is free. The meeting will retain its original duration even when delayed.
  3. Rooms are allocated to meetings based on their original start times, with earlier meetings getting priority.

Meetings are represented by half-closed intervals [start, end), which include the start time but not the end time. The objective is to find the room number that has the most meetings by the end. And if there's a tie, we are interested in the room with the lowest number.

Intuition

The solution is based on sorting and using heaps (priority queues). Here's the intuition step by step:

  1. Sorting the Meetings: We first sort the meetings by their start time. This ensures that we always consider meetings in the order they are meant to start, which is important for fairness and aligns with the problem constraints.

  2. Using Two Heaps: We maintain two heaps (priority queues):

    • idle: A min-heap of available rooms.
    • busy: A min-heap of rooms currently occupied by meetings, with their expected free time as the key.

    By default, all n rooms are added to idle heap to indicate they are available.

  3. Processing Meetings: We iterate through each meeting after sorting. For each meeting:

    • We first free up rooms in the busy heap where meetings have ended—i.e., rooms with free time less than or equal to the current meeting's start time.
    • We then check if there's an available room in the idle heap. If there is, we take the one at the top (lowest number) and schedule the current meeting there.
    • If there isn't an available room, we look in the busy heap for the room that will become available first, delay the current meeting until this room is free, and reschedule with the same duration.
  4. Counting Meetings per Room: We use an array cnt to keep track of the number of meetings in each room. Every time a meeting is scheduled in a room, we increment the count for that room.

  5. Finding the Room with Most Meetings: After scheduling all meetings, we find the room that has the highest count in cnt. In case of a tie, the iteration ensures that the room with the lowest number prevails due to its earlier index in array.

The function ends by returning the index (room number) that had the most meetings.

The Python code implements this intuition using the heapq module, which provides an implementation for min-heaps in Python.

Solution Approach

The solution implements an efficient approach using sorting and heap data structures to manage the rooms and their availability. Here's a detailed walkthrough:

  1. Sort the Meetings: The meetings are sorted by their start time to ensure we process them in the correct order.

    1meetings.sort()
  2. Initialization:

    • Create an idle heap, populated with room numbers (0 through n-1). This represents all available rooms.

      1idle = list(range(n))
      2heapify(idle)
    • Create a busy heap to keep track of rooms that are currently in use, along with when they will become free.

    • Have a counter cnt to count the number of meetings for each room.

      1busy = []
      2cnt = [0] * n
  3. Iterating Over Meetings: Loop through each meeting and make decisions based on room availability.

    1for s, e in meetings:
  4. Freeing Up Rooms: Before scheduling a meeting, check if any meetings have ended, and if so, move those rooms from the busy heap back to the idle heap.

    1while busy and busy[0][0] <= s:
    2    heappush(idle, heappop(busy)[1])
  5. Scheduling Meetings:

    • If there are available rooms (idle is not empty), pop the lowest-numbered room and schedule the current meeting in that room. Then push the room along with the new end time onto the busy heap and increment the corresponding room count.

      1if idle:
      2    i = heappop(idle)
      3    cnt[i] += 1
      4    heappush(busy, (e, i))
    • If no rooms are available, pull the room from the busy heap that will become available first. Delay the current meeting until this room is free, maintain its duration, and push it back onto the busy heap with the updated end time. Also, increment the corresponding room count.

      1else:
      2    a, i = heappop(busy)
      3    cnt[i] += 1
      4    heappush(busy, (a + e - s, i))
  6. Finding the Room with Most Meetings: After processing all meetings, iterate over the cnt list to find the room number that has the highest count (most meetings). In the case of a tie, the loop ensures that the earliest room number is chosen.

    1ans = 0
    2for i, v in enumerate(cnt):
    3    if cnt[ans] < v:
    4        ans = i
  7. Return the Result: The variable ans holds the room number that hosted the most meetings, and we return it from the function.

    1return ans

This approach cleverly uses sorting to handle meetings in chronological order and heaps to manage room availability efficiently. The heap data structure allows us to access the room that will become free soonest in O(log n) time, which is much faster than linear search. The result is a well-considered solution that efficiently processes meetings and room allocations, satisfying all given constraints.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's consider an example to illustrate the solution approach step by step.

Assuming we have 3 rooms (n = 3) and four meetings with the following start and end times meetings = [(1, 4), (2, 3), (3, 5), (5, 6)].

  1. Sort the Meetings: After sorting based on start times, meetings remains the same as the input is already sorted.

  2. Initialization:

    • The idle heap is initialized with [0, 1, 2], representing three available rooms.
    • The busy heap is empty initially, as no meetings are taking place.
    • The cnt list is initialized to [0, 0, 0] to track the number of meetings in each room.
  3. First Meeting (1, 4):

    • The idle heap has [0, 1, 2], we take out room 0 for our meeting and update the busy heap to [(4, 0)].
    • The cnt array is updated to [1, 0, 0].
  4. Second Meeting (2, 3):

    • Still, before scheduling, we check for free rooms. None are free.
    • The idle heap has [1, 2]. We use room 1 and now the busy heap is [(3, 1), (4, 0)].
    • The cnt array is updated to [1, 1, 0].
  5. Third Meeting (3, 5):

    • Before this meeting, room 1 becomes free. So the busy heap becomes [(4, 0)] and idle heap is [1, 2].
    • Room 1 is reused, and now busy heap is [(4, 0), (5, 1)].
    • The cnt array is updated to [1, 2, 0].
  6. Fourth Meeting (5, 6):

    • Before this meeting, room 0 becomes free. busy now is [(5, 1)] and idle is [0, 2].
    • Meeting takes place in room 0, and busy heap is [(6, 0), (5, 1)].
    • The cnt array is updated to [2, 2, 0].
  7. Finding the Room with Most Meetings:

    • After processing all meetings, we observe that the cnt array is [2, 2, 0].
    • Rooms 0 and 1 both hosted two meetings. Due to the iteration, the result will be the lower-numbered room in case of a tie; thus, room 0 is the answer.
  8. Return the Result: The function would return 0 as the room that hosted the most meetings in this example.

Python Solution

1from heapq import heapify, heappop, heappush
2
3class Solution:
4    def mostBooked(self, n: int, meetings: list[list[int]]) -> int:
5        # Sort meetings by start time
6        meetings.sort()
7      
8        # Initialize a heap for tracking busy rooms and idle rooms
9        busy_rooms_heap = []
10        idle_rooms_heap = list(range(n))
11        heapify(idle_rooms_heap)
12      
13        # Initialize a counter to track number of meetings for each room
14        meeting_count = [0] * n
15      
16        # Iterate over sorted meetings
17        for start_time, end_time in meetings:
18            # Free up rooms that have finished their meeting before current meeting starts
19            while busy_rooms_heap and busy_rooms_heap[0][0] <= start_time:
20                room_index = heappop(busy_rooms_heap)[1]
21                heappush(idle_rooms_heap, room_index)
22          
23            # If there's an idle room, use it
24            if idle_rooms_heap:
25                room_index = heappop(idle_rooms_heap)
26                meeting_count[room_index] += 1
27                heappush(busy_rooms_heap, (end_time, room_index))
28            else:
29                # No idle rooms; wait for the first available room
30                earliest_end, room_index = heappop(busy_rooms_heap)
31                meeting_count[room_index] += 1
32              
33                # Schedule the meeting in the now available room and push it back onto the busy heap
34                heappush(busy_rooms_heap, (earliest_end + end_time - start_time, room_index))
35      
36        # Find the room with the most meetings booked
37        most_booked_room = 0
38        for i, count in enumerate(meeting_count):
39            if meeting_count[most_booked_room] < count:
40                most_booked_room = i
41              
42        return most_booked_room
43
44# Test example
45# Instantiate the class
46solution = Solution()
47
48# Example usage
49n = 2
50meetings = [[0, 10], [0, 5], [10, 15]]
51most_booked = solution.mostBooked(n, meetings)
52print("The most booked room is:", most_booked)  # Output will depend on the input
53

Java Solution

1class Solution {
2  
3    // Function to find the room that gets booked the most
4    public int mostBooked(int n, int[][] meetings) {
5        // Sort all the meetings by their start time
6        Arrays.sort(meetings, (a, b) -> a[0] - b[0]);
7      
8        // Priority queue to keep track of busy rooms
9        // Sort by end time; if end times are same, sort by room id
10        PriorityQueue<int[]> busyRooms = new PriorityQueue<>(
11                (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
12      
13        // Priority queue for idle rooms, sorted by room id
14        PriorityQueue<Integer> idleRooms = new PriorityQueue<>();
15      
16        // Initialize all rooms as idle
17        for (int i = 0; i < n; i++) {
18            idleRooms.offer(i);
19        }
20      
21        // Counter for the number of meetings each room has
22        int[] count = new int[n];
23      
24        // Iterate over all meetings
25        for (int[] meeting : meetings) {
26            int start = meeting[0], end = meeting[1];
27          
28            // Free up rooms that have finished their meeting before the start of the current meeting
29            while (!busyRooms.isEmpty() && busyRooms.peek()[0] <= start) {
30                idleRooms.offer(busyRooms.poll()[1]);
31            }
32          
33            // Choose a room for the current meeting
34            int roomId;
35            if (!idleRooms.isEmpty()) {
36                // If there is an idle room available, use the one with the smallest id
37                roomId = idleRooms.poll();
38                // Add the meeting to the busy queue with the new end time and the room id
39                busyRooms.offer(new int[] {end, roomId});
40            } else {
41                // If no idle room is available, wait for the next room to be free
42                int[] busyRoom = busyRooms.poll();
43                roomId = busyRoom[1];
44                // Schedule the meeting in this room, adjusting the meeting length accordingly
45                busyRooms.offer(new int[] {busyRoom[0] + end - start, roomId});
46            }
47          
48            // Increment the count of meetings for the chosen room
49            count[roomId]++;
50        }
51      
52        // Find the room with the maximum number of meetings booked
53        int mostBookedRoom = 0;
54        for (int i = 0; i < n; i++) {
55            if (count[mostBookedRoom] < count[i]) {
56                mostBookedRoom = i;
57            }
58        }
59      
60        // Return the room id with the highest booking count
61        return mostBookedRoom;
62    }
63}
64

C++ Solution

1#include <vector>
2#include <queue>
3#include <algorithm>
4
5using std::vector;
6using std::priority_queue;
7using std::pair;
8using std::sort;
9using std::greater;
10
11using ll = long long;
12using RoomTimePair = pair<ll, int>; // A pair of time to room mapping.
13
14class Solution {
15public:
16    int mostBooked(int n, vector<vector<int>>& meetings) {
17        priority_queue<int, vector<int>, greater<int>> availableRooms; // Min-heap for idle rooms, sorted by room index.
18        priority_queue<RoomTimePair, vector<RoomTimePair>, greater<RoomTimePair>> occupiedRooms; // Min-heap for busy rooms, sorted by ending time.
19      
20        // Initialize all rooms as available.
21        for (int i = 0; i < n; ++i) {
22            availableRooms.push(i);
23        }
24      
25        vector<int> bookingCount(n, 0); // Count of bookings for each room.
26      
27        // Sort meetings based on their start time.
28        sort(meetings.begin(), meetings.end());
29      
30        // Process each meeting.
31        for (auto& meeting : meetings) {
32            ll startTime = meeting[0];
33            ll endTime = meeting[1];
34          
35            // Free up rooms that are no longer busy.
36            while (!occupiedRooms.empty() && occupiedRooms.top().first <= startTime) {
37                availableRooms.push(occupiedRooms.top().second);
38                occupiedRooms.pop();
39            }
40          
41            int roomIndex;
42            if (!availableRooms.empty()) {
43                // If there is an available room, assign the meeting to the room with the smallest index.
44                roomIndex = availableRooms.top();
45                availableRooms.pop();
46                occupiedRooms.push({endTime, roomIndex});
47            } else {
48                // If no rooms are available, wait for the next room to become free.
49                auto nextAvailableRoom = occupiedRooms.top();
50                occupiedRooms.pop();
51                roomIndex = nextAvailableRoom.second;
52                occupiedRooms.push({nextAvailableRoom.first + (endTime - startTime), roomIndex});
53            }
54          
55            // Increment the booking count for the selected room.
56            bookingCount[roomIndex]++;
57        }
58      
59        // Find the room with the maximum number of bookings.
60        int mostBookedRoomIndex = 0;
61        for (int i = 0; i < n; ++i) {
62            if (bookingCount[mostBookedRoomIndex] < bookingCount[i]) {
63                mostBookedRoomIndex = i;
64            }
65        }
66        return mostBookedRoomIndex; // Return the index of the room that's been most booked.
67    }
68};
69

Typescript Solution

1type RoomTimePair = [number, number]; // Tuple to represent time to room mapping.
2
3// Utility function to sort RoomTimePairs based on the first element (time)
4function sortRoomTimePairs(a: RoomTimePair, b: RoomTimePair): number {
5    return a[0] - b[0];
6}
7
8// Utility function to sort numbers in ascending order
9function sortNumbersAscending(a: number, b: number): number {
10    return a - b;
11}
12
13// Maintains a Min-heap for idle rooms, sorted by room index.
14let availableRooms: number[] = [];
15
16// Maintains a Min-heap for busy rooms, sorted by ending time.
17let occupiedRooms: RoomTimePair[] = [];
18
19// Contains the count of bookings for each room.
20let bookingCount: number[] = [];
21
22// Inserts an element into the Min-heap for available rooms.
23function pushAvailableRooms(roomIndex: number) {
24    availableRooms.push(roomIndex);
25    availableRooms.sort(sortNumbersAscending);
26}
27
28// Extracts the smallest element from the Min-heap of available rooms.
29function popAvailableRooms(): number {
30    return availableRooms.shift()!;
31}
32
33// Inserts an element into the Min-heap for occupied rooms.
34function pushOccupiedRooms(roomTime: RoomTimePair) {
35    occupiedRooms.push(roomTime);
36    occupiedRooms.sort(sortRoomTimePairs);
37}
38
39// Extracts the smallest element from the Min-heap of occupied rooms.
40function popOccupiedRooms(): RoomTimePair {
41    return occupiedRooms.shift()!;
42}
43
44// Function to determine the most booked meeting room
45function mostBooked(n: number, meetings: number[][]): number {
46    // Initialize all rooms as available.
47    for (let i = 0; i < n; i++) {
48        pushAvailableRooms(i);
49        bookingCount[i] = 0;
50    }
51
52    // Sort meetings based on their start time.
53    meetings.sort((a, b) => a[0] - b[0]);
54
55    // Process each meeting.
56    for (let meeting of meetings) {
57        let startTime: number = meeting[0];
58        let endTime: number = meeting[1];
59
60        // Free up rooms that are no longer busy.
61        while (occupiedRooms.length > 0 && occupiedRooms[0][0] <= startTime) {
62            pushAvailableRooms(popOccupiedRooms()[1]);
63        }
64
65        let roomIndex: number;
66        if (availableRooms.length > 0) {
67            // Assign the meeting to the room with the smallest index if available.
68            roomIndex = popAvailableRooms();
69            pushOccupiedRooms([endTime, roomIndex]);
70        } else {
71            // Wait for the next room to become free if no rooms are available.
72            let nextAvailableRoom = popOccupiedRooms();
73            roomIndex = nextAvailableRoom[1];
74            pushOccupiedRooms([nextAvailableRoom[0] + (endTime - startTime), roomIndex]);
75        }
76
77        // Increment the booking count for the selected room.
78        bookingCount[roomIndex]++;
79    }
80
81    // Find the room with the maximum number of bookings.
82    let mostBookedRoomIndex = 0;
83    for (let i = 0; i < n; i++) {
84        if (bookingCount[mostBookedRoomIndex] < bookingCount[i]) {
85            mostBookedRoomIndex = i;
86        }
87    }
88
89    return mostBookedRoomIndex; // Return the index of the room that's been most booked.
90}
91
92// Example usage:
93// let n = 2;
94// let meetings = [[0, 10], [1, 5], [2, 7]];
95// console.log(mostBooked(n, meetings)); // Expected output: the index of the most booked room
96

Time and Space Complexity

Time Complexity

The time complexity of the solution is determined by several factors:

  1. Sorting the meetings list: This step has a complexity of O(M log M), where M is the number of meetings.

  2. Iterating through meetings: Each meeting is processed once, adding an O(M) factor.

  3. Maintaining the busy heap: Each meeting can lead to a push and pop operation. The heap operations take O(log N), where N is the number of rooms. In the worst case, all meetings require an operation, adding an O(M log N) factor.

  4. Maintaining the idle heap: Similar to the busy heap, each operation can take O(log N). Since operations are conducted whenever a room becomes free or is used, this operation also contributes O(M log N) to the complexity.

The mentioned operations are all that are required, so the total time complexity is O(M log M) + O(M) + O(M log N) + O(M log N). Given that O(M log M) is the dominating factor, we can approximate the total time complexity to O(M log M).

Space Complexity

The space complexity of the solution is determined by the storage used:

  1. Arrays cnt and idle: Both of these use O(N) space where N is the number of rooms.

  2. Heap busy: In the worst case, the busy heap may store details of all N rooms, so it uses O(N) space.

  3. Sorted meetings list: This list is sorted in-place, so it does not use extra space beyond the initial input list.

The total space complexity is therefore O(N), derived from the largest storage component used in the algorithm.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫