Loading problems...
TL;DR: The optimal solution uses two Priority Queues—one to track available rooms by index and another to track occupied rooms by end time—to efficiently simulate the meeting schedule and handle delays.
In LeetCode 2402, we are given rooms and a list of meeting intervals. We must allocate meetings to rooms based on specific rules: prioritize the lowest-numbered available room, and if all rooms are occupied, delay the meeting until a room becomes free. Our goal is to determine which room hosts the most meetings, breaking ties by choosing the room with the lower index.
This problem, known as Meeting Rooms III, is a popular interview question that tests your ability to manage resources and simulate time-based events efficiently using heap data structures.
The brute force approach attempts to simulate the allocation process by iterating through the sorted meetings and checking the status of every room for each meeting.
For each meeting :
start.Pseudo-code:
textsort(meetings) room_availability_times = array of size n (initialized to 0) meeting_counts = array of size n (initialized to 0) for each meeting (start, end): best_room = -1 min_availability = infinity found_unused = false // Scan all rooms for i from 0 to n-1: if room_availability_times[i] <= start: if not found_unused: best_room = i found_unused = true // Since we iterate 0 to n-1, the first valid one is the lowest index break if room_availability_times[i] < min_availability: min_availability = room_availability_times[i] best_room = i // Update state if found_unused: room_availability_times[best_room] = end else: duration = end - start room_availability_times[best_room] += duration meeting_counts[best_room]++
Why it is suboptimal: The time complexity is where is the number of meetings and is the number of rooms. While is small (100) in this specific problem, making this approach technically passable, it scales poorly if increases. In an interview setting, demonstrating an approach is preferred to show mastery of data structures.
The core difficulty in LeetCode 2402 is efficiently managing the state of the rooms. A room can be in one of two states:
The key insight is to maintain two separate Priority Queues (Min-Heaps) to handle these states independently:
unused_rooms: A Min-Heap storing the indices of rooms that are currently free. This allows access to the lowest-numbered available room.engaged_rooms: A Min-Heap storing pairs of {end_time, room_index}. This allows efficient retrieval of the room that will become free soonest.By sorting the meetings by start time, we can process the timeline linearly. Before allocating a room for the current meeting, we "fast-forward" by checking engaged_rooms. Any room with an end_time less than or equal to the current meeting's start_time is moved from engaged_rooms to unused_rooms.
This structure enforces the constraint that we always prioritize the lowest index among all currently available rooms, not just the one that finished most recently.

meetings array by start time to process events chronologically.unused_rooms: Initialize with all room indices to .engaged_rooms: Initialize as empty.start and end:
engaged_rooms. While the top element's end_time start, pop the room and push its index into unused_rooms.unused_rooms is not empty, pop the smallest index. Push {end, index} into engaged_rooms.unused_rooms is empty, we must wait. Pop the room with the earliest end_time from engaged_rooms. Calculate the new end time: new_end = current_room_end + (end - start). Push {new_end, index} back into engaged_rooms.Let's trace the logic with and meetings [[0,10], [1,5], [2,7]].
Initialization:
unused_rooms: [0, 1]engaged_rooms: []count: [0, 0]Meeting [0, 10]:
engaged_rooms is empty. No action.unused_rooms has [0, 1]. Pop 0.engaged_rooms gets {10, 0}.count: [1, 0]Meeting [1, 5]:
engaged_rooms is {10, 0}. , so no rooms released.unused_rooms has [1]. Pop 1.engaged_rooms gets {5, 1}. Heap structure ensures min-element is at top. engaged_rooms roughly [{5, 1}, {10, 0}].count: [1, 1]Meeting [2, 7]:
engaged_rooms is {5, 1}. , so no rooms released.unused_rooms is empty.{5, 1} from engaged_rooms. This room frees up at time 5.Result: Room 1 has 2 meetings, Room 0 has 1. Return 1.
The correctness relies on the invariant maintained by the two heaps.
engaged to unused whenever end_time <= start, we ensure unused_rooms contains all rooms eligible to take the meeting at the current start time.unused_rooms is a min-heap, extracting the root guarantees we select the lowest-numbered room, satisfying the problem's tie-breaking rule.engaged_rooms min-heap provides the room that minimizes the delay (earliest finish time), which is the greedy choice required to minimize waiting time.cpp#include <vector> #include <queue> #include <algorithm> #include <functional> using namespace std; class Solution { public: int mostBooked(int n, vector<vector<int>>& meetings) { // Sort meetings by start time sort(meetings.begin(), meetings.end()); // Min-heap for available room indices: stores int priority_queue<int, vector<int>, greater<int>> unused_rooms; // Min-heap for engaged rooms: stores {end_time, room_index} // Use long long for time to prevent overflow priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> engaged_rooms; // Initialize all rooms as unused for (int i = 0; i < n; ++i) { unused_rooms.push(i); } vector<int> count(n, 0); for (const auto& meeting : meetings) { long long start = meeting[0]; long long end = meeting[1]; // Release rooms that are done before or at the current meeting's start time while (!engaged_rooms.empty() && engaged_rooms.top().first <= start) { unused_rooms.push(engaged_rooms.top().second); engaged_rooms.pop(); } if (!unused_rooms.empty()) { // Case 1: Room is available int room = unused_rooms.top(); unused_rooms.pop(); engaged_rooms.push({end, room}); count[room]++; } else { // Case 2: No room available, must delay pair<long long, int> earliest = engaged_rooms.top(); engaged_rooms.pop(); long long new_end = earliest.first + (end - start); engaged_rooms.push({new_end, earliest.second}); count[earliest.second]++; } } // Find the room with max meetings (lowest index on tie) int max_meetings = 0; int result_room = 0; for (int i = 0; i < n; ++i) { if (count[i] > max_meetings) { max_meetings = count[i]; result_room = i; } } return result_room; } };
javaimport java.util.*; class Solution { public int mostBooked(int n, int[][] meetings) { // Sort meetings by start time Arrays.sort(meetings, (a, b) -> Integer.compare(a[0], b[0])); // Min-heap for unused rooms (stores room index) PriorityQueue<Integer> unusedRooms = new PriorityQueue<>(); // Min-heap for engaged rooms (stores {end_time, room_index}) // Sort by end time, then by room index PriorityQueue<long[]> engagedRooms = new PriorityQueue<>((a, b) -> { if (a[0] != b[0]) return Long.compare(a[0], b[0]); return Long.compare(a[1], b[1]); }); for (int i = 0; i < n; i++) { unusedRooms.offer(i); } int[] count = new int[n]; for (int[] meeting : meetings) { long start = meeting[0]; long end = meeting[1]; // Release rooms that have finished while (!engagedRooms.isEmpty() && engagedRooms.peek()[0] <= start) { unusedRooms.offer((int) engagedRooms.poll()[1]); } if (!unusedRooms.isEmpty()) { int room = unusedRooms.poll(); engagedRooms.offer(new long[]{end, room}); count[room]++; } else { long[] earliest = engagedRooms.poll(); long finishTime = earliest[0]; int room = (int) earliest[1]; long newEnd = finishTime + (end - start); engagedRooms.offer(new long[]{newEnd, room}); count[room]++; } } int maxMeetings = 0; int resultRoom = 0; for (int i = 0; i < n; i++) { if (count[i] > maxMeetings) { maxMeetings = count[i]; resultRoom = i; } } return resultRoom; } }
pythonimport heapq class Solution: def mostBooked(self, n: int, meetings: List[List[int]]) -> int: # Sort meetings by start time meetings.sort() # Min-heap for unused rooms (integers) unused_rooms = [i for i in range(n)] heapq.heapify(unused_rooms) # Min-heap for engaged rooms (tuples: (end_time, room_index)) engaged_rooms = [] count = [0] * n for start, end in meetings: # Release rooms that finish before or at current start time while engaged_rooms and engaged_rooms[0][0] <= start: _, room = heapq.heappop(engaged_rooms) heapq.heappush(unused_rooms, room) if unused_rooms: room = heapq.heappop(unused_rooms) heapq.heappush(engaged_rooms, (end, room)) count[room] += 1 else: finish_time, room = heapq.heappop(engaged_rooms) new_end = finish_time + (end - start) heapq.heappush(engaged_rooms, (new_end, room)) count[room] += 1 # Find room with max meetings max_meetings = 0 result_room = 0 for i in range(n): if count[i] > max_meetings: max_meetings = count[i] result_room = i return result_room
Let be the number of rooms and be the number of meetings.
Time Complexity:
The Heap - Scheduling pattern used in LeetCode 2402 is highly transferable.
Why did I get a Time Limit Exceeded (TLE)?
{10, 1} to engaged_rooms.count: [1, 2]Space Complexity:
unused_rooms and engaged_rooms).count array takes space.Why is my output wrong for cases with delayed meetings?
engaged_rooms (delayed case), setting the new end time to current_time + duration instead of room_finish_time + duration.Why am I getting Integer Overflow?
int in C++/Java) for time variables.long long (C++) or long (Java/Python handles large ints automatically).Why is the room selection wrong when multiple rooms free up?
engaged_rooms and using that room immediately without checking if a lower-indexed room is also free.unused_rooms first, then pop the min index.