Meeting Rooms III solution and explanation
IBM
Google
9 more videos on this problem
Meeting Rooms III - Leetcode 2402 - PythonNeetCodeIO · 16:16 · 37K views
Meeting Rooms III | Detailed Intuition | Brute Force | Optimal | Leetcode 2402 | codestorywithMIKcodestorywithMIK · 1:00:03 · 21K views
2402. Meeting Rooms III | Leetcode Weekly Contest 309 | LeetCode 2402Bro Coders · 12:37 · 8K views
MEETING ROOMS III | LEETCODE # 2402 | PYTHON HEAP SOLUTIONCracking FAANG · 18:40 · 7K views
2402. Meeting Rooms III | Sorting | Heap(Priority Queue) | Hard 🥶Aryan Mittal · 38:58 · 6K views
Meeting Rooms III | Leetcode 2402Techdose · 27:01 · 3K views
2402. Meeting Rooms III (Leetcode Hard)Programming Live with Larry · 24:56 · 1K views
Leetcode 2402: Meeting Rooms IIIAlgorithms Casts · 18:25 · 646 views
Daily Leetcode #2097: Dec 27, 2025 - 2402. Meeting Rooms IIIProgramming Live with Larry · 17:55 · 503 views
2402. Meeting Rooms III | Leetcode Daily - PythonLeetcode Daily · 8:51 · 319 views
The problem
You are given an integer n. There are n rooms numbered from 0 to n - 1.
You are given a 2D integer array meetings where meetings[i] = [starti, endi] means that a meeting will be held during the half-closed time interval [starti, endi). All the values of starti are unique.
Meetings are allocated to rooms in the following manner:
- Each meeting will take place in the unused room with the lowest number.
- If there are no available rooms, the meeting will be delayed until a room becomes free. The delayed meeting should have the same duration as the original meeting.
- When a room becomes unused, meetings that have an earlier original start time should be given the room.
Return the number of the room that held the most meetings. If there are multiple rooms, return the room with the lowest number.
A half-closed interval [a, b) is the interval between a and b including a and not including b.
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 <= 1001 <= meetings.length <= 105meetings[i].length == 20 <= starti < endi <= 5 * 105- All the values of
startiare unique.
Approach overview
Problem Overview: You are given n meeting rooms and a list of meeting time intervals. Each meeting must be assigned to the lowest indexed available room. If no room is free, the meeting waits until the earliest room becomes available. After scheduling all meetings, return the room that handled the most meetings.
Approach 1: Priority Queue with Room Availability Tracking (O(m log n) time, O(n) space)
This is the standard optimal approach. First sort meetings by start time using sorting. Maintain two min-heaps: one heap for available rooms (ordered by room index) and another for occupied rooms storing (endTime, roomId). As you iterate through meetings, release rooms whose end time is less than or equal to the current start time. If a room is available, assign the meeting immediately. If not, pop the earliest finishing room and delay the meeting until that time. Track how many meetings each room handles and return the index with the maximum count. Heap operations keep scheduling efficient.
Approach 2: Using Priority Queue for Room Scheduling (O(m log n) time, O(n) space)
This variation focuses on modeling the scheduling process directly. Maintain a min-heap of busy rooms keyed by meeting end time and another heap of free room indices. When processing a meeting, repeatedly pop from the busy heap until rooms become free. If no room is free, extend the meeting start to the earliest end time and reuse that room. This is effectively a scheduling simulation powered by a heap (priority queue). The approach is common in interview discussions because it cleanly separates room selection and meeting completion events.
Approach 3: Simulation with Event Queue (O(m log n) time, O(n) space)
Another perspective treats the problem as a full simulation. Meetings create "start events" and room releases create "end events". A priority queue processes events in chronological order. When a meeting begins, allocate the smallest available room. If none are available, reschedule the meeting when the next room frees up. This approach mirrors real-world scheduling systems and helps when implementing the logic in languages like C++ with explicit event handling.
Approach 4: Sorting and Greedy Allocation (O(m log n) time, O(n) space)
A greedy strategy works after sorting meetings by start time. Always assign the earliest available room with the smallest index. If all rooms are busy, greedily select the meeting that finishes first and extend its timeline. Internally this still relies on a heap to efficiently track the earliest finishing meeting, but the reasoning focuses on greedy scheduling rather than explicit simulation. Concepts from array processing and interval scheduling drive the logic.
Recommended for interviews: The priority queue with room availability tracking is what most interviewers expect. It demonstrates understanding of interval scheduling, heaps, and simulation. Starting with a basic simulation shows you understand the constraints, but implementing the two-heap optimal approach proves you can design scalable scheduling systems.
Approach 1: Priority Queue with Room Availability Tracking
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.
import heapq
from collections import defaultdict
def mostBooked(n, meetings):
meetings.sort()
room_heap = list(range(n))
heapq.heapify(room_heap)
end_times = []
room_usage = [0] * n
for start, end in meetings:
while end_times and end_times[0][0] <= start:
_, room = heapq.heappop(end_times)
heapq.heappush(room_heap, room)
if room_heap:
room = heapq.heappop(room_heap)
room_usage[room] += 1
heapq.heappush(end_times, (end, room))
else:
earliest_end, room = heapq.heappop(end_times)
duration = end - start
new_end = earliest_end + duration
room_usage[room] += 1
heapq.heappush(end_times, (new_end, room))
return room_usage.index(max(room_usage))The 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.
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.
Approach 2: Simulation with Event Queue
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.
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
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()));
}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.
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.
Approach 3: Using Priority Queue for Room Scheduling
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.
import heapq
def mostBooked(n, meetings):
meetings.sort()
count = [0] * n
available_rooms = list(range(n))
heapq.heapify(available_rooms)
busy_rooms = []
for start, end in meetings:
while busy_rooms and busy_rooms[0][0] <= start:
_, room = heapq.heappop(busy_rooms)
heapq.heappush(available_rooms, room)
if available_rooms:
room = heapq.heappop(available_rooms)
heapq.heappush(busy_rooms, (end, room))
count[room] += 1
else:
end_time, room = heapq.heappop(busy_rooms)
duration = end - start
new_end_time = end_time + duration
heapq.heappush(busy_rooms, (new_end_time, room))
count[room] += 1
max_count = max(count)
for i in range(n):
if count[i] == max_count:
return i
if __name__ == "__main__":
meetings = [[0, 10], [1, 5], [2, 7], [3, 4]]
print(mostBooked(2, meetings)) # Output: 0import java.util.*;
public class MeetingRooms {
public int mostBooked(int n, int[][] meetings) {
Arrays.sort(meetings, Comparator.comparingInt(a -> a[0]));
int[] roomCount = new int[n];
PriorityQueue<Integer> availableRooms = new PriorityQueue<>();
PriorityQueue<int[]> busyRooms = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
for (int i = 0; i < n; i++) {
availableRooms.offer(i);
}
for (int[] meeting : meetings) {
while (!busyRooms.isEmpty() && busyRooms.peek()[0] <= meeting[0]) {
availableRooms.offer(busyRooms.poll()[1]);
}
if (!availableRooms.isEmpty()) {
int room = availableRooms.poll();
roomCount[room]++;
busyRooms.offer(new int[]{meeting[1], room});
} else {
int[] nextAvailable = busyRooms.poll();
roomCount[nextAvailable[1]]++;
busyRooms.offer(new int[]{nextAvailable[0] + (meeting[1] - meeting[0]), nextAvailable[1]});
}
}
int maxBookings = 0;
int roomWithMostBookings = 0;
for (int i = 0; i < n; i++) {
if (roomCount[i] > maxBookings) {
maxBookings = roomCount[i];
roomWithMostBookings = i;
}
}
return roomWithMostBookings;
}
public static void main(String[] args) {
MeetingRooms mr = new MeetingRooms();
int[][] meetings = {{0, 10}, {1, 5}, {2, 7}, {3, 4}};
System.out.println(mr.mostBooked(2, meetings)); // Output: 0
}
}#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct Room {
int id, endTime;
Room(int id, int endTime) : id(id), endTime(endTime) {}
bool operator>(const Room& other) const { return endTime > other.endTime; }
};
int mostBooked(int n, vector<vector<int>>& meetings) {
sort(meetings.begin(), meetings.end());
vector<int> count(n, 0);
priority_queue<Room, vector<Room>, greater<Room>> pq;
for (int i = 0; i < n; ++i) {
pq.emplace(i, 0);
}
for (const auto& meeting : meetings) {
while (!pq.empty() && pq.top().endTime q;
for (int i = 0; i < n; ++i) {
pq.push({0, i});
}
for (const auto& meeting : meetings) {
while (!finished.empty() && finished.top().first <= meeting[0]) {
pq.push({finished.top().second, finished.top().second});
finished.pop();
}
if (!pq.empty()) {
int room = pq.top().second;
pq.pop();
roomCount[room]++;
finished.push({meeting[1], room});
} else {
auto earliest = finished.top(); finished.pop();
int room = earliest.second;
roomCount[room]++;
finished.push({earliest.first + (meeting[1] - meeting[0]), room});
}
}
int maxCount = *max_element(roomCount.begin(), roomCount.end());
for (int i = 0; i < n; i++) {
if (roomCount[i] == maxCount) return i;
}
return -1;
}
int main() {
vector<vector<int>> meetings = {{0,10},{1,5},{2,7},{3,4}};
cout << mostBooked(2, meetings) << endl; // Output: 0
return 0;
}const mostBooked = (n, meetings) => {
meetings.sort((a, b) => a[0] - b[0]);
const roomCount = Array(n).fill(0);
const availableRooms = [...Array(n).keys()];
const busyRooms = [];
for (const [start, end] of meetings) {
while (busyRooms.length && busyRooms[0][0] <= start) {
const [_, room] = busyRooms.shift();
availableRooms.push(room);
availableRooms.sort((a, b) => a - b);
}
if (availableRooms.length) {
const room = availableRooms.shift();
roomCount[room]++;
busyRooms.push([end, room]);
busyRooms.sort((a, b) => a[0] - b[0]);
} else {
const [endTime, room] = busyRooms.shift();
roomCount[room]++;
busyRooms.push([endTime + end - start, room]);
busyRooms.sort((a, b) => a[0] - b[0]);
}
}
const maxCount = Math.max(...roomCount);
return roomCount.indexOf(maxCount);
};
console.log(mostBooked(2, [[0, 10], [1, 5], [2, 7], [3, 4]])); // Output: 0#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
void updateAvailableTime(int *availableRooms, int size, int currentTime) {
for (int i = 0; i < size; ++i) {
if (availableRooms[i] < currentTime) {
availableRooms[i] = currentTime;
}
}
}
int mostBooked(int n, int** meetings, int meetingsSize, int* meetingsColSize) {
int availableRooms[n];
int bookings[n];
for (int i = 0; i < n; ++i) {
availableRooms[i] = 0;
bookings[i] = 0;
}
for (int i = 0; i < meetingsSize; ++i) {
int start = meetings[i][0];
int end = meetings[i][1];
int duration = end - start;
updateAvailableTime(availableRooms, n, start);
int earliest = INT_MAX;
int roomIndex = -1;
for (int j = 0; j < n; ++j) {
if (availableRooms[j] <= start && availableRooms[j] < earliest) {
earliest = availableRooms[j];
roomIndex = j;
}
}
if (roomIndex == -1) {
// all rooms are booked
earliest = INT_MAX;
for (int j = 0; j < n; ++j) {
if (availableRooms[j] < earliest) {
earliest = availableRooms[j];
roomIndex = j;
}
}
availableRooms[roomIndex] += duration;
} else {
availableRooms[roomIndex] = end;
}
bookings[roomIndex]++;
}
int maxBookings = 0;
int roomWithMostBookings = 0;
for (int i = 0; i < n; ++i) {
if (bookings[i] > maxBookings) {
maxBookings = bookings[i];
roomWithMostBookings = i;
}
}
return roomWithMostBookings;
}
int main() {
int n = 2;
int meetingsSize = 4;
int meetingsColSize[4];
int* meetings[4];
for (int i = 0; i < meetingsSize; ++i) {
meetingsColSize[i] = 2;
meetings[i] = (int*)malloc(2 * sizeof(int));
}
meetings[0][0] = 0; meetings[0][1] = 10;
meetings[1][0] = 1; meetings[1][1] = 5;
meetings[2][0] = 2; meetings[2][1] = 7;
meetings[3][0] = 3; meetings[3][1] = 4;
printf("Output: %d\n", mostBooked(n, meetings, meetingsSize, meetingsColSize));
return 0;
}using System;
using System.Collections.Generic;
public class MeetingRooms {
public int MostBooked(int n, int[][] meetings) {
Array.Sort(meetings, (a, b) => a[0].CompareTo(b[0]));
int[] count = new int[n];
SortedSet<(int endTime, int room)> busyRooms = new SortedSet<(int, int)>();
SortedSet<int> availableRooms = new SortedSet<int>();
for (int i = 0; i < n; i++) availableRooms.Add(i);
foreach (var meeting in meetings) {
int start = meeting[0], end = meeting[1];
while (busyRooms.Count > 0 && busyRooms.Min.endTime <= start) {
var room = busyRooms.Min;
busyRooms.Remove(room);
availableRooms.Add(room.room);
}
if (availableRooms.Count > 0) {
int room = availableRooms.Min;
availableRooms.Remove(room);
count[room]++;
busyRooms.Add((end, room));
} else {
var earliestAvailable = busyRooms.Min;
busyRooms.Remove(earliestAvailable);
int room = earliestAvailable.room;
count[room]++;
busyRooms.Add((earliestAvailable.endTime + (end - start), room));
}
}
int maxCount = 0, roomWithMostBookings = 0;
for (int i = 0; i < n; i++) {
if (count[i] > maxCount) {
maxCount = count[i];
roomWithMostBookings = i;
}
}
return roomWithMostBookings;
}
public static void Main() {
MeetingRooms mr = new MeetingRooms();
int[][] meetings = new int[][] { new[] {0, 10}, new[] {1, 5}, new[] {2, 7}, new[] {3, 4} };
Console.WriteLine(mr.MostBooked(2, meetings));
}
}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.
Time Complexity: O(m log n), owing to heap operations for n rooms over m meetings.
Space Complexity: O(n), for managing room assignments in the heaps.
Approach 4: Sorting and Greedy Allocation
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.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
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;
}#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
int *arr1 = *(int **)a;
int *arr2 = *(int **)b;
return arr1[0] - arr2[0];
}
int mostBooked(int n, int** meetings, int meetingsSize, int* meetingsColSize) {
int *ends = (int *)malloc(n * sizeof(int));
int *counts = (int *)malloc(n * sizeof(int));
for (int i = 0; i < n; ++i) {
ends[i] = 0;
counts[i] = 0;
}
qsort(meetings, meetingsSize, sizeof(int*), cmp);
for (int i = 0; i < meetingsSize; ++i) {
int start = meetings[i][0];
int end = meetings[i][1];
int duration = end - start;
int bestRoom = -1, earliestEnd = 1e9;
for (int j = 0; j < n; ++j) {
if (ends[j] <= start) {
bestRoom = j;
break;
}
if (ends[j] < earliestEnd) {
earliestEnd = ends[j];
bestRoom = j;
}
}
if (ends[bestRoom] <= start) {
ends[bestRoom] = end;
} else {
ends[bestRoom] += duration;
}
counts[bestRoom]++;
}
int maxCount = 0, roomWithMostBookings = 0;
for (int i = 0; i < n; ++i) {
if (counts[i] > maxCount) {
maxCount = counts[i];
roomWithMostBookings = i;
}
}
free(ends);
free(counts);
return roomWithMostBookings;
}
int main() {
int n = 2;
int *meetings[] = {(int[]){0, 10}, (int[]){1, 5}, (int[]){2, 7}, (int[]){3, 4}};
int meetingsColSize[] = {2, 2, 2, 2};
printf("%d\n", mostBooked(n, meetings, 4, meetingsColSize)); // Output: 0
return 0;
}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.
Time Complexity: O(m * n), due to dynamic room checks for each meeting sequence requiring inner iteration.
Space Complexity: O(n), handling room end times and usage counts.
Approach 5: Priority Queue (Min-Heap)
We define two priority queues to represent idle meeting rooms and busy meeting rooms respectively. The idle meeting rooms idle are sorted by index; the busy meeting rooms busy are sorted by end time and index.
First, sort the meetings by start time, then iterate through the meetings. For each meeting:
- If there are busy meeting rooms with end time less than or equal to the current meeting's start time, add them to the idle meeting rooms queue
idle; - If there are idle meeting rooms available, take the room with the smallest index from the idle queue
idleand add it to the busy queuebusy; - If there are no idle meeting rooms, find the room with the earliest end time and smallest index from the busy queue
busy, and add it back to the busy queuebusy.
The time complexity is O(m (log m + log n)), and the space complexity is O(n + m), where n and m are the number of meeting rooms and meetings respectively.
Similar problems:
function mostBooked(n: number, meetings: number[][]): number {
meetings.sort((a, b) => a[0] - b[0]);
const idle = new MinPriorityQueue<number>();
for (let i = 0; i < n; ++i) {
idle.enqueue(i);
}
const busy = new PriorityQueue<[number, number]>((a, b) => {
if (a[0] === b[0]) {
return a[1] - b[1];
}
return a[0] - b[0];
});
const cnt: number[] = new Array(n).fill(0);
for (const v of meetings) {
const s = v[0],
e = v[1];
while (!busy.isEmpty() && busy.front()[0] <= s) {
const i = busy.dequeue()[1];
idle.enqueue(i);
}
let i = 0;
if (!idle.isEmpty()) {
i = idle.dequeue();
busy.enqueue([e, i]);
} else {
const x = busy.dequeue();
i = x[1];
busy.enqueue([x[0] + e - s, i]);
}
++cnt[i];
}
let ans = 0;
for (let i = 0; i < n; ++i) {
if (cnt[ans] < cnt[i]) {
ans = i;
}
}
return ans;
}func mostBooked(n int, meetings [][]int) int {
sort.Slice(meetings, func(i, j int) bool { return meetings[i][0] < meetings[j][0] })
idle := hp{make([]int, n)}
for i := 0; i < n; i++ {
idle.IntSlice[i] = i
}
busy := hp2{}
cnt := make([]int, n)
for _, v := range meetings {
s, e := v[0], v[1]
for len(busy) > 0 && busy[0].end <= s {
heap.Push(&idle, heap.Pop(&busy).(pair).i)
}
var i int
if idle.Len() > 0 {
i = heap.Pop(&idle).(int)
heap.Push(&busy, pair{e, i})
} else {
x := heap.Pop(&busy).(pair)
i = x.i
heap.Push(&busy, pair{x.end + e - s, i})
}
cnt[i]++
}
ans := 0
for i, v := range cnt {
if cnt[ans] < v {
ans = i
}
}
return ans
}
type hp struct{ sort.IntSlice }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
a := h.IntSlice
v := a[len(a)-1]
h.IntSlice = a[:len(a)-1]
return v
}
type pair struct{ end, i int }
type hp2 []pair
func (h hp2) Len() int { return len(h) }
func (h hp2) Less(i, j int) bool {
a, b := h[i], h[j]
return a.end < b.end || a.end == b.end && a.i < b.i
}
func (h hp2) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp2) Push(v any) { *h = append(*h, v.(pair)) }
func (h *hp2) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }Complexity comparison
| Approach | Complexity |
|---|---|
| Priority Queue with Room Availability Tracking | 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). |
| Simulation with Event Queue | 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. |
| Using Priority Queue for Room Scheduling | Time Complexity: O(m log n), owing to heap operations for n rooms over m meetings. |
| Sorting and Greedy Allocation | Time Complexity: O(m * n), due to dynamic room checks for each meeting sequence requiring inner iteration. |
| Priority Queue (Min-Heap) | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Priority Queue with Room Availability Tracking | O(m log n) | O(n) | Best general solution for interviews and production scheduling problems |
| Priority Queue Room Scheduling | O(m log n) | O(n) | When modeling busy and free rooms separately for clarity |
| Simulation with Event Queue | O(m log n) | O(n) | Useful when implementing a full event-driven simulation |
| Sorting and Greedy Allocation | O(m log n) | O(n) | When reasoning about interval scheduling and greedy strategies |
Frequently asked questions
Is Meeting Rooms III easy or hard?
Meeting Rooms III is classified as a Hard problem on LeetCode. The difficulty comes from combining interval scheduling, heap-based resource management, and simulation while correctly handling delayed meetings.
Meeting Rooms III Python or Java solution
Most implementations use two heaps. In Python, the heapq module manages available and busy rooms efficiently. Java solutions typically rely on PriorityQueue with custom comparators for end times and room indices.
How to solve Meeting Rooms III in O(m log n)?
Sort the meetings by start time, then maintain two heaps: one for available rooms ordered by index and another for occupied rooms ordered by end time. Before scheduling a meeting, release rooms whose meetings have ended. If no room is free, delay the meeting until the earliest room becomes available. Each scheduling step uses heap operations, giving O(m log n) complexity.
What is the best approach for Meeting Rooms III?
The optimal solution uses two priority queues. One heap stores available room indices and another tracks busy rooms by their meeting end time. Meetings are processed in sorted order, freeing rooms when their end time passes. This approach schedules each meeting with efficient heap operations and runs in O(m log n) time.
What data structure is used in Meeting Rooms III?
The core data structure is a min-heap (priority queue). One heap tracks the earliest finishing meeting and another keeps available room indices sorted. Arrays are used to count how many meetings each room handles.
What is the time complexity of Meeting Rooms III?
The dominant cost comes from heap operations during scheduling. After sorting the meetings in O(m log m), each meeting may trigger push and pop operations on heaps of size at most n. The overall complexity is O(m log n) time with O(n) extra space.
Is Meeting Rooms III asked at Google, Amazon, or Meta?
Meeting room scheduling and interval allocation problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants of Meeting Rooms I, II, and III are common because they test heaps, greedy scheduling, and simulation skills in one problem.