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:
- Each meeting is scheduled in the lowest-numbered room available.
- 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.
- 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:
-
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.
-
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 toidle
heap to indicate they are available. -
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.
- We first free up rooms in the
-
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. -
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.
Learn more about Sorting and Heap (Priority Queue) patterns.
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:
-
Sort the Meetings: The
meetings
are sorted by their start time to ensure we process them in the correct order.meetings.sort()
-
Initialization:
-
Create an
idle
heap, populated with room numbers (0 throughn-1
). This represents all available rooms.idle = list(range(n)) heapify(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.busy = [] cnt = [0] * n
-
-
Iterating Over Meetings: Loop through each meeting and make decisions based on room availability.
for s, e in meetings:
-
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 theidle
heap.while busy and busy[0][0] <= s: heappush(idle, heappop(busy)[1])
-
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 thebusy
heap and increment the corresponding room count.if idle: i = heappop(idle) cnt[i] += 1 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 thebusy
heap with the updated end time. Also, increment the corresponding room count.else: a, i = heappop(busy) cnt[i] += 1 heappush(busy, (a + e - s, i))
-
-
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.ans = 0 for i, v in enumerate(cnt): if cnt[ans] < v: ans = i
-
Return the Result: The variable
ans
holds the room number that hosted the most meetings, and we return it from the function.return 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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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)]
.
-
Sort the Meetings: After sorting based on start times,
meetings
remains the same as the input is already sorted. -
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.
- The
-
First Meeting
(1, 4)
:- The
idle
heap has[0, 1, 2]
, we take out room0
for our meeting and update thebusy
heap to[(4, 0)]
. - The
cnt
array is updated to[1, 0, 0]
.
- The
-
Second Meeting
(2, 3)
:- Still, before scheduling, we check for free rooms. None are free.
- The
idle
heap has[1, 2]
. We use room1
and now thebusy
heap is[(3, 1), (4, 0)]
. - The
cnt
array is updated to[1, 1, 0]
.
-
Third Meeting
(3, 5)
:- Before this meeting, room
1
becomes free. So thebusy
heap becomes[(4, 0)]
andidle
heap is[1, 2]
. - Room
1
is reused, and nowbusy
heap is[(4, 0), (5, 1)]
. - The
cnt
array is updated to[1, 2, 0]
.
- Before this meeting, room
-
Fourth Meeting
(5, 6)
:- Before this meeting, room
0
becomes free.busy
now is[(5, 1)]
andidle
is[0, 2]
. - Meeting takes place in room
0
, andbusy
heap is[(6, 0), (5, 1)]
. - The
cnt
array is updated to[2, 2, 0]
.
- Before this meeting, room
-
Finding the Room with Most Meetings:
- After processing all meetings, we observe that the
cnt
array is[2, 2, 0]
. - Rooms
0
and1
both hosted two meetings. Due to the iteration, the result will be the lower-numbered room in case of a tie; thus, room0
is the answer.
- After processing all meetings, we observe that the
-
Return the Result: The function would return
0
as the room that hosted the most meetings in this example.
Solution Implementation
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
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
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
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:
-
Sorting the
meetings
list: This step has a complexity ofO(M log M)
, whereM
is the number of meetings. -
Iterating through
meetings
: Each meeting is processed once, adding anO(M)
factor. -
Maintaining the
busy
heap: Each meeting can lead to a push and pop operation. The heap operations takeO(log N)
, whereN
is the number of rooms. In the worst case, all meetings require an operation, adding anO(M log N)
factor. -
Maintaining the
idle
heap: Similar to thebusy
heap, each operation can takeO(log N)
. Since operations are conducted whenever a room becomes free or is used, this operation also contributesO(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:
-
Arrays
cnt
andidle
: Both of these useO(N)
space whereN
is the number of rooms. -
Heap
busy
: In the worst case, thebusy
heap may store details of allN
rooms, so it usesO(N)
space. -
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.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm is best for finding the shortest distance between two points in an unweighted graph?
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Don’t Miss This!