1. Iterate through all $n$ rooms to find which ones are free at start.
2. If any rooms are free, pick the one with the lowest index.
3. If no rooms are free, scan all $n$ rooms to find the one that finishes earliest. Calculate the delay and update that room's availability.
4. Update the meeting count for the chosen room.

Pseudo-code:

text
sort(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 $O(M \cdot N)$ where $M$ is the number of meetings and $N$ is the number of rooms. While $N$ is small (100) in this specific problem, making this approach technically passable, it scales poorly if $N$ increases. In an interview setting, demonstrating an $O(M \log N)$ approach is preferred to show mastery of data structures.

Core Insight for Meeting Rooms III

The core difficulty in LeetCode 2402 is efficiently managing the state of the rooms. A room can be in one of two states:

1. Unused (Available): We need to pick the room with the lowest index.
2. Engaged (Occupied): We need to know when it becomes free.

The key insight is to maintain two separate Priority Queues (Min-Heaps) to handle these states independently:

1. unused_rooms: A Min-Heap storing the indices of rooms that are currently free. This allows $O(1)$ access to the lowest-numbered available room.
2. 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.

Algorithm Strategy: Heap (Priority Queue)

1. Sort Meetings: Sort the input meetings array by start time to process events chronologically.
2. Initialize Heaps:
   • unused_rooms: Initialize with all room indices $0$ to $n-1$.
   • engaged_rooms: Initialize as empty.
3. Process Meetings: Iterate through the sorted meetings. For each meeting with start and end:
   • Release Rooms: Check engaged_rooms. While the top element's end_time $\le$ start, pop the room and push its index into unused_rooms.
   • Allocate Room:
     • Case A (Room Available): If unused_rooms is not empty, pop the smallest index. Push {end, index} into engaged_rooms.
     • Case B (No Room Available): If 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.
4. Track Counts: Increment the counter for the room index chosen in step 3.
5. Result: Return the index with the maximum count (lowest index breaks ties).

Execution Flow

Let's trace the logic with $n=2$ and meetings [[0,10], [1,5], [2,7]].

1. Initialization:

   • unused_rooms: [0, 1]
   • engaged_rooms: []
   • count: [0, 0]

2. Meeting [0, 10]:

   • Release: engaged_rooms is empty. No action.
   • Allocate: unused_rooms has [0, 1]. Pop 0.
   • Update: engaged_rooms gets {10, 0}.
   • count: [1, 0]

3. Meeting [1, 5]:

   • Release: Top of engaged_rooms is {10, 0}. $10 > 1$, so no rooms released.
   • Allocate: unused_rooms has [1]. Pop 1.
   • Update: engaged_rooms gets {5, 1}. Heap structure ensures min-element is at top. engaged_rooms roughly [{5, 1}, {10, 0}].
   • count: [1, 1]

4. Meeting [2, 7]:

   • Release: Top of engaged_rooms is {5, 1}. $5 > 2$, so no rooms released.
   • Allocate: unused_rooms is empty.
   • Delay Logic: Pop {5, 1} from engaged_rooms. This room frees up at time 5.
   • New Duration: $7 - 2 = 5$.

5. Result: Room 1 has 2 meetings, Room 0 has 1. Return 1.

Proof of Correctness

The correctness relies on the invariant maintained by the two heaps.

1. Availability Constraint: By moving rooms from engaged to unused whenever end_time <= start, we ensure unused_rooms contains all rooms eligible to take the meeting at the current start time.
2. Priority Constraint: Since unused_rooms is a min-heap, extracting the root guarantees we select the lowest-numbered room, satisfying the problem's tie-breaking rule.
3. Delay Logic: When no rooms are free, the engaged_rooms min-heap provides the room that minimizes the delay (earliest finish time), which is the greedy choice required to minimize waiting time.

Reference Implementation

C++ Solution for LeetCode 2402

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;
    }
};

Java Solution for LeetCode 2402

java
import 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;
    }
}

Python Solution for LeetCode 2402

python
import 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