2402.会议室 III：优先队列大模拟

【LetMeFly】2402.会议室 III：优先队列大模拟

力扣题目链接：https://leetcode.cn/problems/meeting-rooms-iii/

给你一个整数 n ，共有编号从 0 到 n - 1 的 n 个会议室。

给你一个二维整数数组 meetings ，其中 meetings[i] = [starti, endi] 表示一场会议将会在 半闭 时间区间 [starti, endi) 举办。所有 starti 的值 互不相同 。

会议将会按以下方式分配给会议室：

1. 每场会议都会在未占用且编号 最小 的会议室举办。
2. 如果没有可用的会议室，会议将会延期，直到存在空闲的会议室。延期会议的持续时间和原会议持续时间 相同 。
3. 当会议室处于未占用状态时，将会优先提供给原 开始 时间更早的会议。

返回举办最多次会议的房间 编号 。如果存在多个房间满足此条件，则返回编号 最小 的房间。

半闭区间 [a, b) 是 a 和 b 之间的区间，包括 a 但 不包括 b 。

 

示例 1：

输入：n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
输出：0
解释：
- 在时间 0 ，两个会议室都未占用，第一场会议在会议室 0 举办。
- 在时间 1 ，只有会议室 1 未占用，第二场会议在会议室 1 举办。
- 在时间 2 ，两个会议室都被占用，第三场会议延期举办。
- 在时间 3 ，两个会议室都被占用，第四场会议延期举办。
- 在时间 5 ，会议室 1 的会议结束。第三场会议在会议室 1 举办，时间周期为 [5,10) 。
- 在时间 10 ，两个会议室的会议都结束。第四场会议在会议室 0 举办，时间周期为 [10,11) 。
会议室 0 和会议室 1 都举办了 2 场会议，所以返回 0 。 

示例 2：

输入：n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
输出：1
解释：
- 在时间 1 ，所有三个会议室都未占用，第一场会议在会议室 0 举办。
- 在时间 2 ，会议室 1 和 2 未占用，第二场会议在会议室 1 举办。
- 在时间 3 ，只有会议室 2 未占用，第三场会议在会议室 2 举办。
- 在时间 4 ，所有三个会议室都被占用，第四场会议延期举办。 
- 在时间 5 ，会议室 2 的会议结束。第四场会议在会议室 2 举办，时间周期为 [5,10) 。
- 在时间 6 ，所有三个会议室都被占用，第五场会议延期举办。 
- 在时间 10 ，会议室 1 和 2 的会议结束。第五场会议在会议室 1 举办，时间周期为 [10,12) 。 
会议室 1 和会议室 2 都举办了 2 场会议，所以返回 1 。 

 

提示：

• 1 <= n <= 100
• 1 <= meetings.length <= 105
• meetings[i].length == 2
• 0 <= starti < endi <= 5 * 105
• starti 的所有值 互不相同

解题方法：大模拟——两个优先队列

有没有发现这道题有严格的顺序优先级，使用优先队列再合适不过了。

先想想我们的策略，再思考具体怎么模拟：

遍历按开始时间递增的会议（因为开始时间早是安排会议的优先级依据），对于某个待安排的会议：

1. 查看到会议开始时间为止有没有新释放的会议室

2. 查看此刻有没有空的会议室

   1. 如果有，则使用编号最小的那个会议室
   2. 否则，等待到一个会议室释放为止并使用之（同一时间多会议室到期则优先释放编号较小的那个）

多清晰的流水线啊，只需要用代码将其表现出来就好了。

1. 对于会议，只需要按照开始时间从小到大排个序，因为会议的安排顺序是严格按照开始时间安排的且开始时间互不相同。
2. 对于会议室的使用（空闲会议室），优先使用编号最小的，所以可以使用一个优先队列来存放空闲会议室。
3. 对于在使用的会议室，优先释放结束时间最早的那个，有释放时间相同则优先释放编号较小的那个，所以也可以使用一个优先队列来维护。

注意，$10^5$个$5\times10^5$可能会超过int32。

• 时间复杂度$O(m\log m + n\log n + m\log n)$，其中$m=len(meetings)$。$m\log m$来自会议的排序，$n\log n$来自$n$个会议室初始状态的入队，$m\log n$来自每个会议的会议室分配；
• 空间复杂度$O(n)$。

AC代码

C++

/*
 * @LastEditTime: 2025-12-27 23:36:34
 */
typedef long long ll;  // 10^5个5*10^5可能会超int32!
class Solution {
public:
    int mostBooked(int n, vector<vector<int>>& meetings) {
        sort(meetings.begin(), meetings.end());
        priority_queue<int, vector<int>, greater<>> canuse;
        for (int i = 0; i < n; i++) {
            canuse.push(i);
        }
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> inuse;
        vector<int> times(n);
        for (vector<int>& meeting : meetings) {
            // 先看有没有新释放的
            while (!inuse.empty() && inuse.top().first <= meeting[0]) {
                auto[_, thisRoom] = inuse.top();
                canuse.push(thisRoom);
                inuse.pop();
            }
            int thisRoom;
            ll endTime;
            // 看看有没有空的
            if (!canuse.empty()) {
                thisRoom = canuse.top();
                endTime = meeting[1];
                canuse.pop();
            } else {  // 等到第一个释放
                auto[freeTime, room] = inuse.top();
                thisRoom = room;
                endTime = freeTime + meeting[1] - meeting[0];
                inuse.pop();
            }
            times[thisRoom]++;
            inuse.push({endTime, thisRoom});
        }
        return max_element(times.begin(), times.end()) - times.begin();
    }
};

#if defined(_WIN32) || defined(__APPLE__)
/*
2
[[0,10],[1,5],[2,7],[3,4]]

0
*/
int main() {
    int n;
    string s;
    while (cin >> n >> s) {
        Solution sol;
        vector<vector<int>> v = stringToVectorVector(s);
        cout << sol.mostBooked(n, v) << endl;
    }
    return 0;
}
#endif

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源