双堆模拟

作者

2402. 会议室 III – 力扣（LeetCode）

class Solution {
public:
    int mostBooked(int n, vector<vector<int>>& meetings) {
        ranges::sort(meetings, {}, [](auto& m) {return m[0];});
​
        // 空闲会议室
        priority_queue<int, vector<int>, greater<>> idle;
        for (int i = 0; i < n; i++)
        {
            idle.push(i);
        }
​
        // （结束事件， 会议编号）
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> using_;
        // 每个会议室使用次数
        vector<int> cnt(n);
​
        for (auto& m : meetings)
        {
            long long start = m[0], end = m[1];
​
            // 在start时刻有的空闲会议室
            while (!using_.empty() && using_.top().first <= start)
            {
                idle.push(using_.top().second);
                using_.pop();
            }
​
            int i;
            // 如果有空闲会议室
            if (!idle.empty())
            {
                i = idle.top();
                idle.pop();
            }
            else // 没有空闲会议室
            {
                auto [e, room] = using_.top();
                i = room;
                using_.pop();
                end += e - start;
            }
​
            // 使用一个会议室
            using_.emplace(end, i); 
            cnt[i]++;
        }
​
        return ranges::max_element(cnt) - cnt.begin();
    }
};

1. 核心目标与定位

该算法旨在解决一个受限资源分配问题：

  • 输入：n 个会议室，一组带有开始和结束时间的会议。
  • 规则：按开始时间顺序处理；空闲时优先用小编号会议室；全满时等待最早空闲的会议室并整体推迟会议。
  • 输出：使用频率最高的会议室编号（若次数相同取编号最小者）。

2. 技术选型与数据结构（为什么这么选？）

报告中通过对比，明确了三个关键工具：

  • 排序（Sort）：通过 ranges::sort 确保处理逻辑符合时间线（O(M \log M)）。
  • 双小顶堆（Dual Min-Heaps）：
    • idle：存储空闲会议室编号，保证 O(log N) 获取“编号最小”的资源。
    • using_：存储 {结束时间, 编号}，保证 O(log N) 获取“最早结束”的会议室。
  • 计数数组（Vector）：O(1) 随机访问，记录每个房间的使用频次。

3. 算法执行流程（核心逻辑）

算法通过一个主循环对会议进行“模拟分发”，分为三个关键动作：

  1. 释放（Release）：在处理新会议前，检查 using_ 堆顶。若其结束时间 \le 当前会议开始时间，则将其“移回” idle 堆。
  2. 决策（Decision）：
    • 有空位：从 idle 取出最小编号，会议按原计划开始。
    • 无空位（核心创新点）：从 using_ 强制取出最早结束的房间。关键逻辑：由于产生了等待，新会议的结束时间需要顺延（end = 房间空闲时间 + 会议持续时间）。
  3. 更新（Update）：将房间重新放入 using_ 堆，并给该房间的计数器 cnt[i] 加一。

4. 复杂度与优势分析

  • 性能：总时间复杂度为 O(M \log M + M \log N)，空间复杂度为 O(N)。在处理大规模数据（如 10^5 级别）时具有极高的效率。
  • 优势：
    • 准确性：通过调整 end 时间，完美模拟了会议延迟的物理过程。
    • 简洁性：利用 C++ 现代特性（如 ranges 和结构化绑定）使代码非常易读。

总结：

这份分析深刻抓住了“状态转换（空闲 \leftrightarrow 使用）”这一核心，并解释了如何利用优先级队列来规避暴力搜索的低效。

发表评论