Sponsored
Sponsored
This approach involves using a priority queue (min-heap) to manage room availability and another priority queue to track which meetings are currently taking place. The idea is to process the meetings in order of their start times, allocating them to the earliest available room when possible.
We use two heaps: one to keep track of the earliest finish time of meetings in each room, and another to handle room availability. This ensures that delayed meetings are processed as soon as a room becomes free.
Time Complexity: O((m + n) * log(n)), where m is the number of meetings and n is the number of rooms. Sorting the meetings takes O(m log m), and handling the heaps for each meeting takes O(log n).
Space Complexity: O(n + m), used for storing the room_heap and end_times.
1
2import heapq
3from collections import defaultdict
4
5def mostBooked(n, meetings):
6 meetings.sort()
7 room_heap = list(range(n))
8 heapq.heapify(room_heap)
9 end_times = []
10 room_usage = [0] * n
11
12 for start, end in meetings:
13 while end_times and end_times[0][0] <= start:
14 _, room = heapq.heappop(end_times)
15 heapq.heappush(room_heap, room)
16 if room_heap:
17 room = heapq.heappop(room_heap)
18 room_usage[room] += 1
19 heapq.heappush(end_times, (end, room))
20 else:
21 earliest_end, room = heapq.heappop(end_times)
22 duration = end - start
23 new_end = earliest_end + duration
24 room_usage[room] += 1
25 heapq.heappush(end_times, (new_end, room))
26
27 return room_usage.index(max(room_usage))
28The solution sorts the meetings and uses two heaps: room_heap to track available room numbers and end_times to track when rooms will become free. We loop through the sorted meetings and allocate them either to an immediately available room or delay them as needed. The room usage counter is updated each time a room is assigned a meeting.
This method simulates time progression by using an event queue to handle meeting starting and ending events. The key is to manage events such that at any point, we know which room becomes available next, and we can decide room allocation accordingly.
We use a heap to prioritize events primarily by time, then by starting or ending to handle adjustments when a room frees up.
Time Complexity: O((m + n) * log(n)), where m is the number of meetings and n is the number of rooms. Sorting meetings takes O(m log m), and each meeting's start/end is handled in O(log n) due to the priority queues.
Space Complexity: O(n + m), for the available rooms queue, ongoing meetings queue, and usage tracker.
1
2#include <vector>
3#include <queue>
4#include <algorithm>
5
6using namespace std;
7
int mostBooked(int n, vector<vector<int>>& meetings) {
sort(meetings.begin(), meetings.end());
priority_queue<int, vector<int>, greater<int>> availableRooms;
for (int i = 0; i < n; ++i) availableRooms.push(i);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> ongoingMeetings;
vector<int> roomUsage(n, 0);
for (const auto& meeting : meetings) {
int start = meeting[0];
int end = meeting[1];
while (!ongoingMeetings.empty() && ongoingMeetings.top().first <= start) {
availableRooms.push(ongoingMeetings.top().second);
ongoingMeetings.pop();
}
if (!availableRooms.empty()) {
int room = availableRooms.top();
availableRooms.pop();
ongoingMeetings.push({end, room});
roomUsage[room]++;
} else {
auto earliestEndMeeting = ongoingMeetings.top();
ongoingMeetings.pop();
availableRooms.push(earliestEndMeeting.second);
meeting[0] = earliestEndMeeting.first;
ongoingMeetings.push({earliestEndMeeting.first + end - start, earliestEndMeeting.second});
roomUsage[earliestEndMeeting.second]++;
}
}
return distance(roomUsage.begin(), max_element(roomUsage.begin(), roomUsage.end()));
}
This approach leverages a priority queue to efficiently manage room availability and meeting allocation. We will sort the meetings by their start time. As we iterate through these meetings, we use a priority queue to track the rooms and their next available time. The queue helps in quickly finding the soonest available room, or if a room is currently available. This allows us to allocate or delay the meetings accordingly.
Time Complexity: O(m * n), where m is the number of meetings and n is the number of rooms, mainly due to iterating over the rooms to find availability.
Space Complexity: O(n), where n is the number of rooms, for maintaining the arrays for booking and availability.
This method involves sorting and maintaining room states via a greedy algorithm. We prioritize actively managing room occupation intervals without relying on complex data structures, focusing on maintaining an iterative timeline across sorted meetings to achieve room bookings.
Time Complexity: O(m * n), where m is the number of meetings and n is the number of rooms due to the iteration over rooms.
Space Complexity: O(n), as it maintains end times and booking counts for each room.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
int mostBooked(int n, vector<vector<int>>& meetings) {
sort(meetings.begin(), meetings.end());
vector<int> endTimes(n, 0), count(n, 0);
for (const auto& meeting : meetings) {
int start = meeting[0], end = meeting[1];
int duration = end - start;
int bestRoom = -1, earliestEnd = INT_MAX;
for (int i = 0; i < n; ++i) {
if (endTimes[i] <= start) {
bestRoom = i;
break;
}
if (endTimes[i] < earliestEnd) {
earliestEnd = endTimes[i];
bestRoom = i;
}
}
if (endTimes[bestRoom] <= start) {
endTimes[bestRoom] = end;
} else {
endTimes[bestRoom] += duration;
}
count[bestRoom]++;
}
return max_element(count.begin(), count.end()) - count.begin();
}
int main() {
vector<vector<int>> meetings = {{0, 10}, {1, 5}, {2, 7}, {3, 4}};
cout << mostBooked(2, meetings) << endl; // Output: 0
return 0;
}The solution processes meeting events by sorting them and using two priority queues: availableRooms to track available room numbers and ongoingMeetings to track meetings that are currently taking place. The simulation iterates over sorted meeting times to either assign a room immediately or adjust its start based on available room times.
This Python solution sorts the meetings by start time and uses two heaps. The first heap handles available rooms, and the second keeps track of busy rooms by their next available times. This allows efficient room scheduling and meeting allocation.
This C++ solution sorts the meetings by their start time and tries to allocate a room based on earliest availability or extends the meeting length if rooms are unavailable for immediate allocation. The room with the most counts is ultimately selected.