会议室 III 图解题解

这道题到底在问什么

输入

n=3, meetings=[[1,20],[2,10],[3,5],[4,9],[6,8]]

输出

1

最优解：一步一步想明白

1. 3记住这句:每场会议先「把到点的房从 busy 退回 free」,再「有空房用编号最小、没空房延后到最早空出」。下面每一帧都在套它。
2. 4开局所有房都空闲,free 小根堆里是编号 0、1、2,堆顶 0 是最小编号。busy 堆(右侧面板)是空的,还没有房在用。
3. 5第 1 场会议来了,区间 [1, 20),时长 19。先看有没有房到点该退回空闲:把 busy 堆里结束时间 ≤ 1 的房弹回 free。
4. 6此时 busy 堆是空的,没有正在用的房,直接进入分配。
5. 7free 里有空房,弹堆顶房0(编号最小)给这场会议。它正常占用到本场 end=20。房0 使用次数加到 1。把「20@房0」塞进 busy 堆。
6. 8第 1 场落定:房0 用到 20(写进 busy 堆,右侧面板按结束时间重新冒泡)。现在 free=[1, 2]、busy 有 1 间房在用。继续下一场。
7. 9第 2 场会议来了,区间 [2, 10),时长 8。先看有没有房到点该退回空闲:把 busy 堆里结束时间 ≤ 2 的房弹回 free。
8. 10检查 busy 堆顶:最早空出的房要到 20 才结束,而本场 2 就开始,20 还没到,所以这一步没有房可退回。
9. 11free 里有空房,弹堆顶房1(编号最小)给这场会议。它正常占用到本场 end=10。房1 使用次数加到 1。把「10@房1」塞进 busy 堆。
10. 12第 2 场落定:房1 用到 10(写进 busy 堆,右侧面板按结束时间重新冒泡)。现在 free=[2]、busy 有 2 间房在用。继续下一场。
11. 13第 3 场会议来了,区间 [3, 5),时长 2。先看有没有房到点该退回空闲:把 busy 堆里结束时间 ≤ 3 的房弹回 free。
12. 14检查 busy 堆顶:最早空出的房要到 10 才结束,而本场 3 就开始,10 还没到,所以这一步没有房可退回。
13. 15free 里有空房,弹堆顶房2(编号最小)给这场会议。它正常占用到本场 end=5。房2 使用次数加到 1。把「5@房2」塞进 busy 堆。
14. 16第 3 场落定:房2 用到 5(写进 busy 堆,右侧面板按结束时间重新冒泡)。现在 free=[空]、busy 有 3 间房在用。继续下一场。
15. 17第 4 场会议来了,区间 [4, 9),时长 5。先看有没有房到点该退回空闲:把 busy 堆里结束时间 ≤ 4 的房弹回 free。
16. 18检查 busy 堆顶:最早空出的房要到 5 才结束,而本场 4 就开始,5 还没到,所以这一步没有房可退回。
17. 19free 空了,没有现成空房,本场要延后。弹 busy 堆顶房2(最早在 5 空出),它一空就接着开这场,新结束 = 原结束 5 + 时长 5 = 10。房2 使用次数加到 2。
18. 20第 4 场落定:房2 用到 10(写进 busy 堆,右侧面板按结束时间重新冒泡)。现在 free=[空]、busy 有 3 间房在用。继续下一场。
19. 21第 5 场会议来了,区间 [6, 8),时长 2。先看有没有房到点该退回空闲:把 busy 堆里结束时间 ≤ 6 的房弹回 free。
20. 22检查 busy 堆顶:最早空出的房要到 10 才结束,而本场 6 就开始,10 还没到,所以这一步没有房可退回。
21. 23free 空了,没有现成空房,本场要延后。弹 busy 堆顶房1(最早在 10 空出),它一空就接着开这场,新结束 = 原结束 10 + 时长 2 = 12。房1 使用次数加到 2。
22. 24第 5 场落定:房1 用到 12(写进 busy 堆,右侧面板按结束时间重新冒泡)。现在 free=[空]、busy 有 3 间房在用。所有会议处理完毕。
23. 25五场会议处理完,使用次数是 房0:1、房1:2、房2:2。房1 和房2 都用了 2 次并列最多,按规则取编号小的,所以答案是房 1。靠「free 按编号、busy 按结束时间」两个堆,每步都能 O(log n) 拿到最小编号空房或最早空出的房。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
import heapq
class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        meetings.sort()
        free = list(range(n))
        heapq.heapify(free)
        busy = []
        count = [0] * n
        for start, end in meetings:
            while busy and busy[0][0] <= start:
                _, room = heapq.heappop(busy)
                heapq.heappush(free, room)
            duration = end - start
            if free:
                room = heapq.heappop(free)
                finish = end
            else:
                t, room = heapq.heappop(busy)
                finish = t + duration
            count[room] += 1
            heapq.heappush(busy, (finish, room))
        return max(range(n), key=lambda i: (count[i], -i))

#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
    int mostBooked(int n, vector<vector<int>>& meetings) {
        sort(meetings.begin(), meetings.end());
        priority_queue<int, vector<int>, greater<int>> free;
        for (int i = 0; i < n; ++i) free.push(i);
        priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> busy;
        vector<int> cnt(n);
        for (auto &m : meetings) {
            long long start = m[0], end = m[1], dur = end - start;
            while (!busy.empty() && busy.top().first <= start) { free.push(busy.top().second); busy.pop(); }
            int room; long long finish;
            if (!free.empty()) { room = free.top(); free.pop(); finish = end; }
            else { auto [t, r] = busy.top(); busy.pop(); room = r; finish = t + dur; }
            cnt[room]++; busy.push({finish, room});
        }
        int ans = 0;
        for (int i = 1; i < n; ++i) if (cnt[i] > cnt[ans]) ans = i;
        return ans;
    }
};

import java.util.*;
class Solution {
    public int mostBooked(int n, int[][] meetings) {
        Arrays.sort(meetings, Comparator.comparingInt(a -> a[0]));
        PriorityQueue<Integer> free = new PriorityQueue<>();
        for (int i = 0; i < n; i++) free.offer(i);
        PriorityQueue<long[]> busy = new PriorityQueue<>((a,b) -> a[0] == b[0] ? Long.compare(a[1], b[1]) : Long.compare(a[0], b[0]));
        int[] cnt = new int[n];
        for (int[] m : meetings) {
            long start = m[0], end = m[1], dur = end - start;
            while (!busy.isEmpty() && busy.peek()[0] <= start) free.offer((int) busy.poll()[1]);
            int room; long finish;
            if (!free.isEmpty()) { room = free.poll(); finish = end; }
            else { long[] cur = busy.poll(); room = (int) cur[1]; finish = cur[0] + dur; }
            cnt[room]++; busy.offer(new long[]{finish, room});
        }
        int ans = 0;
        for (int i = 1; i < n; i++) if (cnt[i] > cnt[ans]) ans = i;
        return ans;
    }
}

复杂度

面试官可能追问