LeetCode 2402: Meeting Rooms III (Two Heaps for Busy/Idle Rooms)
LeetCode 2402HeapSimulationToday we solve LeetCode 2402 - Meeting Rooms III.
Source: https://leetcode.com/problems/meeting-rooms-iii/
English
Problem Summary
Given n meeting rooms numbered 0..n-1 and meetings [start, end], assign each meeting to the smallest-index available room. If no room is free at its start time, delay the meeting until the earliest room becomes free, while keeping its duration unchanged. Return the room index that hosted the most meetings (smallest index on ties).
Key Insight
Use two heaps: one min-heap for idle room indices, and one min-heap for busy rooms ordered by (endTime, roomId). Process meetings by ascending start time.
Brute Force and Limitations
For each meeting, scanning all rooms to find availability is O(n), so total can reach O(mn) for m meetings.
Optimal Algorithm Steps
1) Sort meetings by start time.
2) Before handling current meeting, release all rooms whose end time <= start into idle heap.
3) If idle heap is non-empty, use smallest room index.
4) Otherwise pop earliest-finished busy room and delay meeting to start at that end time.
5) Push updated (newEnd, roomId) to busy heap and count usage.
Complexity Analysis
Time: O(m log n + m log m) (sorting meetings dominates when m is large).
Space: O(n) for heaps and counters.
Common Pitfalls
- Not sorting meetings by start time.
- Wrong tie-break when busy rooms end at same time (must choose smaller room id).
- Losing original meeting duration when delaying.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int mostBooked(int n, int[][] meetings) {
java.util.Arrays.sort(meetings, java.util.Comparator.comparingInt(a -> a[0]));
java.util.PriorityQueue<Integer> idle = new java.util.PriorityQueue<>();
for (int i = 0; i < n; i++) idle.offer(i);
java.util.PriorityQueue<long[]> busy = new java.util.PriorityQueue<>((a, b) -> {
if (a[0] != b[0]) return Long.compare(a[0], b[0]);
return Long.compare(a[1], b[1]);
});
int[] cnt = new int[n];
for (int[] mt : meetings) {
long s = mt[0], e = mt[1];
long dur = e - s;
while (!busy.isEmpty() && busy.peek()[0] <= s) {
idle.offer((int) busy.poll()[1]);
}
int room;
long endTime;
if (!idle.isEmpty()) {
room = idle.poll();
endTime = e;
} else {
long[] x = busy.poll();
room = (int) x[1];
endTime = x[0] + dur;
}
busy.offer(new long[]{endTime, room});
cnt[room]++;
}
int ans = 0;
for (int i = 1; i < n; i++) {
if (cnt[i] > cnt[ans]) ans = i;
}
return ans;
}
}type IdleHeap []int
func (h IdleHeap) Len() int { return len(h) }
func (h IdleHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IdleHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IdleHeap) Push(x any) { *h = append(*h, x.(int)) }
func (h *IdleHeap) Pop() any { old := *h; x := old[len(old)-1]; *h = old[:len(old)-1]; return x }
type Busy struct { end int64; room int }
type BusyHeap []Busy
func (h BusyHeap) Len() int { return len(h) }
func (h BusyHeap) Less(i, j int) bool {
if h[i].end != h[j].end { return h[i].end < h[j].end }
return h[i].room < h[j].room
}
func (h BusyHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *BusyHeap) Push(x any) { *h = append(*h, x.(Busy)) }
func (h *BusyHeap) Pop() any { old := *h; x := old[len(old)-1]; *h = old[:len(old)-1]; return x }
func mostBooked(n int, meetings [][]int) int {
sort.Slice(meetings, func(i, j int) bool { return meetings[i][0] < meetings[j][0] })
idle := &IdleHeap{}
heap.Init(idle)
for i := 0; i < n; i++ { heap.Push(idle, i) }
busy := &BusyHeap{}
heap.Init(busy)
cnt := make([]int, n)
for _, mt := range meetings {
s, e := int64(mt[0]), int64(mt[1])
dur := e - s
for busy.Len() > 0 && (*busy)[0].end <= s {
heap.Push(idle, heap.Pop(busy).(Busy).room)
}
var room int
var endTime int64
if idle.Len() > 0 {
room = heap.Pop(idle).(int)
endTime = e
} else {
x := heap.Pop(busy).(Busy)
room = x.room
endTime = x.end + dur
}
heap.Push(busy, Busy{end: endTime, room: room})
cnt[room]++
}
ans := 0
for i := 1; i < n; i++ {
if cnt[i] > cnt[ans] { ans = i }
}
return ans
}class Solution {
public:
int mostBooked(int n, vector<vector<int>>& meetings) {
sort(meetings.begin(), meetings.end());
priority_queue<int, vector<int>, greater<int>> idle;
for (int i = 0; i < n; i++) idle.push(i);
using P = pair<long long, int>;
priority_queue<P, vector<P>, greater<P>> busy; // (end, room)
vector<int> cnt(n, 0);
for (auto& mt : meetings) {
long long s = mt[0], e = mt[1], dur = e - s;
while (!busy.empty() && busy.top().first <= s) {
idle.push(busy.top().second);
busy.pop();
}
int room;
long long endTime;
if (!idle.empty()) {
room = idle.top(); idle.pop();
endTime = e;
} else {
auto [end0, r] = busy.top(); busy.pop();
room = r;
endTime = end0 + dur;
}
busy.push({endTime, room});
cnt[room]++;
}
int ans = 0;
for (int i = 1; i < n; i++) {
if (cnt[i] > cnt[ans]) ans = i;
}
return ans;
}
};class Solution:
def mostBooked(self, n: int, meetings: list[list[int]]) -> int:
meetings.sort()
idle = list(range(n))
heapq.heapify(idle)
busy: list[tuple[int, int]] = [] # (end_time, room_id)
cnt = [0] * n
for s, e in meetings:
dur = e - s
while busy and busy[0][0] <= s:
_, room = heapq.heappop(busy)
heapq.heappush(idle, room)
if idle:
room = heapq.heappop(idle)
end_time = e
else:
end0, room = heapq.heappop(busy)
end_time = end0 + dur
heapq.heappush(busy, (end_time, room))
cnt[room] += 1
ans = 0
for i in range(1, n):
if cnt[i] > cnt[ans]:
ans = i
return ansclass MinHeap {
constructor(cmp) { this.a = []; this.cmp = cmp; }
size() { return this.a.length; }
top() { return this.a[0]; }
push(x) {
const a = this.a; a.push(x);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (this.cmp(a[p], a[i]) <= 0) break;
[a[p], a[i]] = [a[i], a[p]];
i = p;
}
}
pop() {
const a = this.a;
const res = a[0], x = a.pop();
if (a.length) {
a[0] = x;
let i = 0;
while (true) {
let l = i * 2 + 1, r = l + 1, m = i;
if (l < a.length && this.cmp(a[l], a[m]) < 0) m = l;
if (r < a.length && this.cmp(a[r], a[m]) < 0) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return res;
}
}
/**
* @param {number} n
* @param {number[][]} meetings
* @return {number}
*/
var mostBooked = function(n, meetings) {
meetings.sort((a, b) => a[0] - b[0]);
const idle = new MinHeap((x, y) => x - y);
for (let i = 0; i < n; i++) idle.push(i);
const busy = new MinHeap((x, y) => x[0] === y[0] ? x[1] - y[1] : x[0] - y[0]);
const cnt = new Array(n).fill(0);
for (const [s, e] of meetings) {
const dur = e - s;
while (busy.size() && busy.top()[0] <= s) {
idle.push(busy.pop()[1]);
}
let room, endTime;
if (idle.size()) {
room = idle.pop();
endTime = e;
} else {
const [end0, r] = busy.pop();
room = r;
endTime = end0 + dur;
}
busy.push([endTime, room]);
cnt[room]++;
}
let ans = 0;
for (let i = 1; i < n; i++) {
if (cnt[i] > cnt[ans]) ans = i;
}
return ans;
};中文
题目概述
有 n 个会议室（编号 0..n-1）和若干会议 [start, end]。每个会议优先分配给当前空闲且编号最小的会议室；若开始时无空闲会议室，就把会议延后到最早空出的时间开始，会议时长保持不变。返回使用次数最多的会议室编号（并列取编号更小者）。
核心思路
维护两个最小堆：
- idle：空闲会议室编号最小堆。
- busy：忙碌会议室堆，按 (结束时间, 房间编号) 排序。
按开始时间处理会议即可精确模拟题意。
暴力解法与不足
每个会议都线性扫描全部房间找可用位置，单次 O(n)，总计可到 O(mn)，会议多时较慢。
最优算法步骤
1）先按会议开始时间排序。
2）处理当前会议前，把所有 end <= start 的忙碌房间释放到 idle。
3）若 idle 非空，取最小编号房间直接安排。
4）否则从 busy 取最早结束（若并列取更小编号）的房间并延后会议。
5）把新结束时间写回 busy，并累计该房间次数。
复杂度分析
时间复杂度：O(m log m + m log n)。
空间复杂度：O(n)。
常见陷阱
- 忘记按开始时间排序。
- 忽略 busy 的并列规则（结束时间相同要选编号更小）。
- 延后会议时把时长算错。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int mostBooked(int n, int[][] meetings) {
java.util.Arrays.sort(meetings, java.util.Comparator.comparingInt(a -> a[0]));
java.util.PriorityQueue<Integer> idle = new java.util.PriorityQueue<>();
for (int i = 0; i < n; i++) idle.offer(i);
java.util.PriorityQueue<long[]> busy = new java.util.PriorityQueue<>((a, b) -> {
if (a[0] != b[0]) return Long.compare(a[0], b[0]);
return Long.compare(a[1], b[1]);
});
int[] cnt = new int[n];
for (int[] mt : meetings) {
long s = mt[0], e = mt[1];
long dur = e - s;
while (!busy.isEmpty() && busy.peek()[0] <= s) {
idle.offer((int) busy.poll()[1]);
}
int room;
long endTime;
if (!idle.isEmpty()) {
room = idle.poll();
endTime = e;
} else {
long[] x = busy.poll();
room = (int) x[1];
endTime = x[0] + dur;
}
busy.offer(new long[]{endTime, room});
cnt[room]++;
}
int ans = 0;
for (int i = 1; i < n; i++) {
if (cnt[i] > cnt[ans]) ans = i;
}
return ans;
}
}type IdleHeap []int
func (h IdleHeap) Len() int { return len(h) }
func (h IdleHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IdleHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IdleHeap) Push(x any) { *h = append(*h, x.(int)) }
func (h *IdleHeap) Pop() any { old := *h; x := old[len(old)-1]; *h = old[:len(old)-1]; return x }
type Busy struct { end int64; room int }
type BusyHeap []Busy
func (h BusyHeap) Len() int { return len(h) }
func (h BusyHeap) Less(i, j int) bool {
if h[i].end != h[j].end { return h[i].end < h[j].end }
return h[i].room < h[j].room
}
func (h BusyHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *BusyHeap) Push(x any) { *h = append(*h, x.(Busy)) }
func (h *BusyHeap) Pop() any { old := *h; x := old[len(old)-1]; *h = old[:len(old)-1]; return x }
func mostBooked(n int, meetings [][]int) int {
sort.Slice(meetings, func(i, j int) bool { return meetings[i][0] < meetings[j][0] })
idle := &IdleHeap{}
heap.Init(idle)
for i := 0; i < n; i++ { heap.Push(idle, i) }
busy := &BusyHeap{}
heap.Init(busy)
cnt := make([]int, n)
for _, mt := range meetings {
s, e := int64(mt[0]), int64(mt[1])
dur := e - s
for busy.Len() > 0 && (*busy)[0].end <= s {
heap.Push(idle, heap.Pop(busy).(Busy).room)
}
var room int
var endTime int64
if idle.Len() > 0 {
room = heap.Pop(idle).(int)
endTime = e
} else {
x := heap.Pop(busy).(Busy)
room = x.room
endTime = x.end + dur
}
heap.Push(busy, Busy{end: endTime, room: room})
cnt[room]++
}
ans := 0
for i := 1; i < n; i++ {
if cnt[i] > cnt[ans] { ans = i }
}
return ans
}class Solution {
public:
int mostBooked(int n, vector<vector<int>>& meetings) {
sort(meetings.begin(), meetings.end());
priority_queue<int, vector<int>, greater<int>> idle;
for (int i = 0; i < n; i++) idle.push(i);
using P = pair<long long, int>;
priority_queue<P, vector<P>, greater<P>> busy; // (end, room)
vector<int> cnt(n, 0);
for (auto& mt : meetings) {
long long s = mt[0], e = mt[1], dur = e - s;
while (!busy.empty() && busy.top().first <= s) {
idle.push(busy.top().second);
busy.pop();
}
int room;
long long endTime;
if (!idle.empty()) {
room = idle.top(); idle.pop();
endTime = e;
} else {
auto [end0, r] = busy.top(); busy.pop();
room = r;
endTime = end0 + dur;
}
busy.push({endTime, room});
cnt[room]++;
}
int ans = 0;
for (int i = 1; i < n; i++) {
if (cnt[i] > cnt[ans]) ans = i;
}
return ans;
}
};class Solution:
def mostBooked(self, n: int, meetings: list[list[int]]) -> int:
meetings.sort()
idle = list(range(n))
heapq.heapify(idle)
busy: list[tuple[int, int]] = [] # (end_time, room_id)
cnt = [0] * n
for s, e in meetings:
dur = e - s
while busy and busy[0][0] <= s:
_, room = heapq.heappop(busy)
heapq.heappush(idle, room)
if idle:
room = heapq.heappop(idle)
end_time = e
else:
end0, room = heapq.heappop(busy)
end_time = end0 + dur
heapq.heappush(busy, (end_time, room))
cnt[room] += 1
ans = 0
for i in range(1, n):
if cnt[i] > cnt[ans]:
ans = i
return ansclass MinHeap {
constructor(cmp) { this.a = []; this.cmp = cmp; }
size() { return this.a.length; }
top() { return this.a[0]; }
push(x) {
const a = this.a; a.push(x);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (this.cmp(a[p], a[i]) <= 0) break;
[a[p], a[i]] = [a[i], a[p]];
i = p;
}
}
pop() {
const a = this.a;
const res = a[0], x = a.pop();
if (a.length) {
a[0] = x;
let i = 0;
while (true) {
let l = i * 2 + 1, r = l + 1, m = i;
if (l < a.length && this.cmp(a[l], a[m]) < 0) m = l;
if (r < a.length && this.cmp(a[r], a[m]) < 0) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return res;
}
}
/**
* @param {number} n
* @param {number[][]} meetings
* @return {number}
*/
var mostBooked = function(n, meetings) {
meetings.sort((a, b) => a[0] - b[0]);
const idle = new MinHeap((x, y) => x - y);
for (let i = 0; i < n; i++) idle.push(i);
const busy = new MinHeap((x, y) => x[0] === y[0] ? x[1] - y[1] : x[0] - y[0]);
const cnt = new Array(n).fill(0);
for (const [s, e] of meetings) {
const dur = e - s;
while (busy.size() && busy.top()[0] <= s) {
idle.push(busy.pop()[1]);
}
let room, endTime;
if (idle.size()) {
room = idle.pop();
endTime = e;
} else {
const [end0, r] = busy.pop();
room = r;
endTime = end0 + dur;
}
busy.push([endTime, room]);
cnt[room]++;
}
let ans = 0;
for (let i = 1; i < n; i++) {
if (cnt[i] > cnt[ans]) ans = i;
}
return ans;
};
Comments