当前位置：首页 > news >正文

LeetCode 3885.设计事件管理器

news 2026/8/16 3:42:24

给你一组初始事件列表，其中每个事件有一个唯一的 eventId 和一个 priority（优先级）。

实现 EventManager 类：

EventManager(int[][] events) 使用给定事件初始化管理器，其中 events[i] = [eventIdi, priorityi]。
void updatePriority(int eventId, int newPriority) 更新具有 id 为 eventId 的活跃事件的优先级为 newPriority。
int pollHighest() 移除并返回具有最高优先级的活跃事件的 eventId。如果有多个活动事件具有相同的优先级，则返回 eventId 最小的事件。如果没有活跃事件，则返回 -1。
如果一个事件没有被 pollHighest() 移除，则称其为活跃事件。

示例 1：

输入：
[“EventManager”, “pollHighest”, “updatePriority”, “pollHighest”, “pollHighest”]
[[[[5, 7], [2, 7], [9, 4]]], [], [9, 7], [], []]

输出：
[null, 2, null, 5, 9]

解释

EventManager eventManager = new EventManager([[5,7], [2,7], [9,4]]); // 使用三个事件初始化管理器
eventManager.pollHighest(); // 两个事件 5 和 2 的优先级均为 7，因此返回 id 最小的事件 2
eventManager.updatePriority(9, 7); // 将事件 9 的优先级更新为 7
eventManager.pollHighest(); // 剩下的优先级最高的事件是 5 和 9，返回 5
eventManager.pollHighest(); // 返回 9
示例 2：

输入：
[“EventManager”, “pollHighest”, “pollHighest”, “pollHighest”]
[[[[4, 1], [7, 2]]], [], [], []]

输出：
[null, 7, 4, -1]

解释

EventManager eventManager = new EventManager([[4,1], [7,2]]); // 使用两个事件初始化管理器
eventManager.pollHighest(); // 返回 7
eventManager.pollHighest(); // 返回 4
eventManager.pollHighest(); // 没有剩余事件，返回 -1

提示：

1 <= events.length <= 105^55
events[i] = [eventId, priority]
1 <= eventId <= 109^99
1 <= priority <= 109^99
events 中的所有 eventId 值都是唯一的。
1 <= newPriority <= 109^99
对每次调用 updatePriority，eventId 都指向一个活跃事件。
对 updatePriority 和 pollHighest 的总调用次数最多为 105^55次。

懒删除堆，我们可以维护一个优先级和事件id的最大堆，以及一个事件Id到优先级的哈希表。每次updatePriority时，先修改哈希表，然后不删除堆中当前事件id的优先级，而是插入一个新的正确节点进堆；每次pollHighest时，检查当前堆顶事件id的优先级是否是哈希表中存放的优先级，如果是，就找到了优先级最高的事件，否则堆顶就是失效的事件：

classEventManager{public:EventManager(vector<vector<int>>&events){for(vector<int>&event:events){eventToPriority[event[0]]=event[1];heap.push_back({event[1],-event[0]});}make_heap(heap.begin(),heap.end());}voidupdatePriority(inteventId,intnewPriority){eventToPriority[eventId]=newPriority;heap.push_back({newPriority,-eventId});push_heap(heap.begin(),heap.end());}intpollHighest(){while(!heap.empty()&&(eventToPriority.find(-heap[0][1])==eventToPriority.end()||heap[0][0]!=eventToPriority[-heap[0][1]])){pop_heap(heap.begin(),heap.end());heap.pop_back();}if(heap.empty()){return-1;}intans=-heap[0][1];pop_heap(heap.begin(),heap.end());heap.pop_back();eventToPriority.erase(ans);returnans;}private:unordered_map<int,int>eventToPriority;vector<vector<int>>heap;};/** * Your EventManager object will be instantiated and called as such: * EventManager* obj = new EventManager(events); * obj->updatePriority(eventId,newPriority); * int param_2 = obj->pollHighest(); */