)
这道题是经典的会议室 III，核心是双堆模拟，一个堆管空闲会议室（按编号排序），一个堆管正在使用的会议室（按结束时间排序）。
解题思路
1. 排序：按会议开始时间升序排列。
2. 双堆初始化：
- free：小根堆，存空闲会议室编号（0 ~ n-1）。
- busy：小根堆，存 [结束时间, 会议室编号]，按结束时间排序，相同时按编号排序。
3. 遍历会议：
- 先把 busy 中所有结束时间 ≤ 当前会议开始时间的会议室释放回 free。
- 如果 free 不为空 → 取编号最小的空闲会议室。
- 如果 free 为空 → 从 busy 中弹出最早结束的会议室（会议延期），结束时间 = 该会议室的空闲时间 + 当前会议时长。
4. 计数：每次分配会议室时，对应计数 +1。
5. 结果：遍历计数数组，返回举办会议次数最多且编号最小的会议室。
Java 代码实现
import java.util.*;
class Solution {
public int mostBooked(int n, int[][] meetings) {
// 1. 按开始时间排序
Arrays.sort(meetings, (a, b) -> a[0] - b[0]);
// 2. 空闲会议室堆（按编号）
PriorityQueue<Integer> free = new PriorityQueue<>();
for (int i = 0; i < n; i++) free.offer(i);
// 3. 忙碌会议室堆（按结束时间，相同时按编号）
PriorityQueue<long[]> busy = new PriorityQueue<>(
(a, b) -> a[0] != b[0] ? Long.compare(a[0], b[0]) : Long.compare(a[1], b[1])
);
int[] count = new int[n];
// 4. 模拟
for (int[] meeting : meetings) {
long start = meeting[0];
long end = meeting[1];
long duration = end - start;
// 释放已结束的会议室
while (!busy.isEmpty() && busy.peek()[0] <= start) {
free.offer((int) busy.poll()[1]);
}
int room;
if (!free.isEmpty()) {
// 有空闲会议室 → 取编号最小的
room = free.poll();
busy.offer(new long[]{end, room});
} else {
// 无空闲 → 取最早结束的会议室，延期
long[] earliest = busy.poll();
room = (int) earliest[1];
long newEnd = earliest[0] + duration;
busy.offer(new long[]{newEnd, room});
}
count[room]++;
}
// 5. 找结果
int maxCount = 0, ans = 0;
for (int i = 0; i < n; i++) {
if (count[i] > maxCount) {
maxCount = count[i];
ans = i;
}
}
return ans;
}
}
复杂度分析
维度 值
时间复杂度 O(m log m + m log n) —— 排序 O(m log m)，每次堆操作 O(log n)
空间复杂度 O(n + m) —— 两个堆 + 计数数组 + 排序后的会议数组
关键点总结
- 双堆分工明确：free 管编号优先级，busy 管时间优先级。
- 释放逻辑：在每场会议开始前，先释放所有已结束的会议室，保证 free 中的会议室都是真正可用的。
- 延期处理：没有空闲时，直接从 busy 取最早结束的会议室，结束时间 = 原结束时间 + 当前会议时长。
- 注意数据类型：结束时间可能很大，用 long 避免溢出。
