LeetCode · #2402

Meeting Rooms III Solution

You have n rooms numbered 0 to n-1. Schedule meetings in the lowest-numbered available room; if all busy, wait for the earliest to free up. Return the room with the most meetings.

Section One · Problem

Problem Statement

🏷️

Difficulty

Hard

🔗

LeetCode

Problem #2402

🏗️

Pattern

Intervals — two heaps (available + busy)

Given n rooms and sorted meetings[i] = [start, end], assign each meeting to the lowest-numbered available room. If all rooms are busy, delay the meeting until the earliest room frees. Return the room that held the most meetings (ties: lowest number).

Example

Input: n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
Output: 0 // Room 0: meeting[0] at [0,10], then meeting[2] delayed to [10,15]. 2 meetings. // Room 1: meeting[1] at [1,5], then meeting[3] at [5,6]. 2 meetings. // Tie → room 0 (lowest number).

Constraints

• 1 ≤ n ≤ 100 • 1 ≤ meetings.length ≤ 10⁵ • 0 ≤ startᵢ < endᵢ ≤ 5 × 10⁵

Section Two · Approach 1

Brute Force — O(m·n)

For each meeting, scan all n rooms to find the available one with the lowest number or the one that frees earliest.

Problem: O(m·n) where m=meetings, n=rooms. Use two heaps: available rooms (min-heap by room#) and busy rooms (min-heap by free time, then room#). O(m log n).

Java — O(m·n) simulation

 import java.util.*;
class Solution {
public int mostBooked(int n, int[][] meetings) {
        Arrays.sort(meetings, (a,b) -> a[0] - b[0]);
long[] endTime = new long[n];
int[] count = new int[n];
for (int[] m : meetings) {
int best = -1; long earliest = Long.MAX_VALUE;
for (int r = 0; r < n; r++) {
if (endTime[r] <= m[0]) { best = r; break; }
if (endTime[r] < earliest) { earliest = endTime[r]; best = r; }
            }
long start = Math.max(endTime[best], m[0]);
            endTime[best] = start + (m[1] - m[0]);
            count[best]++;
        }
int ans = 0;
for (int r = 1; r < n; r++)
if (count[r] > count[ans]) ans = r;
return ans;
    }
}

Python — O(m·n) simulation

 class Solution:
def mostBooked(self, n: int, meetings: list[list[int]]) -> int:
        meetings.sort()
        end_time = [0] * n
        count = [0] * n
for s, e in meetings:
            best = min(range(n), key=lambda r: (max(end_time[r], s), r)
if end_time[r] <= s
else (end_time[r], r))
# Find earliest available or earliest freeing
avail = [r for r in range(n) if end_time[r] <= s]
if avail: best = min(avail)
else: best = min(range(n), key=lambda r: (end_time[r], r))
            start = max(end_time[best], s)
            end_time[best] = start + (e - s)
            count[best] += 1 return count.index(max(count))

Section Three · Approach 2

Two Heaps — O(m log n)

Maintain two min-heaps: available (free room numbers) and busy (pairs of [freeTime, roomNumber]). For each meeting, move rooms that have freed up from busy → available. Assign to lowest available room, or wait for earliest-freeing busy room.

💡 Mental model: Two queues at a hotel front desk. The "available" queue holds room keys sorted by number. The "busy" queue holds rooms sorted by when they'll be free. For each guest: check if any rooms freed up (transfer keys to available). If available, assign the lowest key. If not, wait for the earliest checkout, assign that room (with delay). Count bookings per room.

Algorithm

Sort meetings by start time.
available = min-heap of [0, 1, ..., n-1]. busy = min-heap of (endTime, roomId).
For each meeting [s, e]:
While busy.peek().endTime ≤ s: move room to available.
If available not empty: assign room = available.poll(). Push (e, room) to busy.
Else: (freeTime, room) = busy.poll(). Push (freeTime + (e-s), room) to busy (delayed).
count[room]++.
Return room with max count (ties: lowest number).

🎯 When to recognize this pattern: "Assign resources by priority with delays." Two heaps (available + busy) is the standard approach for resource scheduling with queuing. Also appears in task scheduler problems and OS scheduling simulations.

Section Four · Trace

Visual Walkthrough

Trace for n=2, meetings=[[0,10],[1,5],[2,7],[3,4]].

Meeting Rooms III — Two Heaps

Section Five · Implementation

Code — Java & Python

Java — Two heaps

 import java.util.*;
class Solution {
public int mostBooked(int n, int[][] meetings) {
        Arrays.sort(meetings, (a,b) -> a[0] - b[0]);
PriorityQueue<Integer> avail = new PriorityQueue<>();
// busy: [endTime, roomId] PriorityQueue<long[]> busy = new PriorityQueue<>(
            (a,b) -> a[0] != b[0] ? Long.compare(a[0],b[0]) : Long.compare(a[1],b[1]));
for (int i = 0; i < n; i++) avail.offer(i);
int[] count = new int[n];
for (int[] m : meetings) {
long start = m[0], dur = m[1] - m[0];
// Free up rooms that ended by now while (!busy.isEmpty() && busy.peek()[0] <= start)
                avail.offer((int) busy.poll()[1]);
if (!avail.isEmpty()) {
int room = avail.poll();
                busy.offer(new long[]{m[1], room});
                count[room]++;
            } else {
long[] earliest = busy.poll();
int room = (int) earliest[1];
                busy.offer(new long[]{earliest[0] + dur, room});
                count[room]++;
            }
        }
int ans = 0;
for (int i = 1; i < n; i++)
if (count[i] > count[ans]) ans = i;
return ans;
    }
}

Python — Two heaps

 import heapq
class Solution:
def mostBooked(self, n: int, meetings: list[list[int]]) -> int:
        meetings.sort()
        avail = list(range(n)) # min-heap of room ids
busy: list[tuple] = [] # (endTime, roomId)
count = [0] * n
for s, e in meetings:
while busy and busy[0][0] <= s:
                _, room = heapq.heappop(busy)
                heapq.heappush(avail, room)
if avail:
                room = heapq.heappop(avail)
                heapq.heappush(busy, (e, room))
else:
                free_time, room = heapq.heappop(busy)
                heapq.heappush(busy, (free_time + e - s, room))
            count[room] += 1 return count.index(max(count))

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Brute simulation	O(m·n)	O(n)	Linear scan per meeting
Two heaps ← optimal	O(m log n)	O(n)	Heap operations for available + busy rooms

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
More rooms than meetings	`n=5, m=2`	Each meeting gets its own room. Most booked: lowest with 1 meeting.
One room	`n=1`	All meetings sequentially delayed. Room 0 has all meetings.
All concurrent	`n=2, [[0,5],[0,5],[0,5]]`	Room 0: [0,5], room 1: [0,5], third waits for room 0 → [5,10].
Delayed chain	`n=1, [[0,10],[1,2],[3,4]]`	All delayed: [0,10],[10,11],[11,12]. Room 0: 3 meetings.
Overflow	Large start/end values	Use `long` for endTime to avoid integer overflow when delays accumulate.

⚠ Common Mistake: Using int for end times. When meetings are delayed, end times accumulate: a meeting originally [0, 500000] delayed 100000 times would overflow. Always use long (Java) or Python's arbitrary-precision ints. Also: when all rooms are busy, the delay duration is e - s (original duration), not e — don't forget to add the delay to the freed room's end time.

← Back to Interval problems

LearningTree

LC 2402 · Meeting Rooms III — Solution & Explanation | DSA Guide