Mastering Meeting Room Scheduling: An Algorithmic Approach
Written on
Understanding the Meeting Room Scheduling Problem
In this section, we explore an intriguing algorithmic challenge that involves managing meeting rooms efficiently. The problem presents a scenario with n rooms, each identified by a number ranging from 0 to n - 1. You are provided with a 2D array called meetings, where each entry meetings[i] = [starti, endi] indicates that a meeting is scheduled during the half-closed time interval [starti, endi). Notably, all starting times are distinct.
The allocation of rooms follows a systematic approach: each meeting is assigned to the lowest-numbered available room. Should all rooms be occupied, the meeting is postponed until a room becomes vacant. It's crucial that the duration of the postponed meeting remains identical to that of the original. When a room becomes available, meetings that were scheduled to start earlier are prioritized.
The objective is to determine which room hosted the highest number of meetings. In cases where multiple rooms share this distinction, the room with the lower number should be returned. A half-closed interval [a, b) includes a but excludes b.
Example 1:
Input: n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
Output: 0
Explanation:
- At time 0, both rooms are idle. The first meeting is assigned to room 0.
- At time 1, room 1 is available. The second meeting starts in room 1.
- At time 2, all rooms are occupied, causing the third meeting to be delayed.
- Similarly, the fourth meeting is also postponed.
- At time 5, the meeting in room 1 concludes, allowing the third meeting to commence in room 1 during the interval [5,10).
- Finally, at time 10, both rooms are free, permitting the fourth meeting to take place in room 0 during the time span [10,11).
Both rooms 0 and 1 each hosted 2 meetings, leading us to return 0.
Example 2:
Input: n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
Output: 1
Explanation:
- Initially, all rooms are free, and the first meeting occurs in room 0.
- As time progresses, the meetings in rooms 1 and 2 are scheduled based on availability.
- The fourth meeting faces delays due to room occupancy but eventually finds a slot in room 2.
- By the end, room 0 has hosted 1 meeting, while rooms 1 and 2 have each held 2 meetings, resulting in the return of 1.
Optimized Approach
The optimized solution utilizes a priority queue to manage room availability. The ready list keeps track of available rooms, while rooms contains the rooms currently in use, represented as [end_time, room_index]. As the meetings are processed in sorted order, rooms that have become free before the start of a new meeting are released. If a room is available, it is assigned to the next meeting; otherwise, the meeting is delayed based on the room that becomes free first.
Python Implementation:
class Solution:
def mostBooked(self, n, meetings):
ready = [r for r in range(n)]
rooms = []
heapify(ready)
res = [0] * n
for s, e in sorted(meetings):
while rooms and rooms[0][0] <= s:
t, r = heappop(rooms)
heappush(ready, r)
if ready:
r = heappop(ready)
heappush(rooms, [e, r])
else:
t, r = heappop(rooms)
heappush(rooms, [t + e - s, r])
res[r] += 1
return res.index(max(res))
C++ Implementation:
bool compare(vector<int>& v1, vector<int>& v2) {
return v1[0] < v2[0];
}
class Solution {
public:
int mostBooked(int n, vector<vector<int>>& meetings) {
sort(meetings.begin(), meetings.end(), compare);
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> engaged;
priority_queue<int, vector<int>, greater<>> unused;
unordered_map<int, int> freq;
for (int i = 0; i < n; i++) {
unused.push(i);}
for (auto x : meetings) {
int s = x[0], e = x[1];
while (!engaged.empty() && engaged.top().first <= s) {
int room = engaged.top().second;
engaged.pop();
unused.push(room);
}
if (!unused.empty()) {
int room = unused.top();
unused.pop();
freq[room] += 1;
engaged.push({e, room});
} else {
auto topmost = engaged.top();
engaged.pop();
freq[topmost.second] += 1;
long long newEnd = topmost.first + (e - s);
engaged.push({newEnd, topmost.second});
}
}
int maxi = 0;
for (int i = 1; i < n; i++) {
if (freq[i] > freq[maxi])
maxi = i;}
return maxi;
}
};
Complexity Analysis
- Time Complexity: O(n * log(n))
- Space Complexity: O(n)
Stay tuned for more intriguing interview questions as I share insights from my experience as a senior software engineer at a FANNG company!
In this video, titled "Meeting Rooms - LeetCode Premium - Coding Interview Questions," you will find a detailed explanation of the meeting room scheduling problem and how to tackle it effectively.
Check out this video titled "Leetcode 252. Meeting Rooms [Algorithm + Code + Time Complexity]," which dives deeper into the algorithmic solutions and the complexities involved in solving this problem.