3885. 设计事件管理器

Medium

题目描述

给定一个初始事件列表，每个事件都有唯一的 eventId 和优先级。

实现 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 <= 10^5
events[i] = [eventId, priority]
1 <= eventId <= 10^9
1 <= priority <= 10^9
events 中所有 eventId 的值都是唯一的
1 <= newPriority <= 10^9
对于每次调用 updatePriority，eventId 都指向一个活跃事件
总共最多调用 10^5 次 updatePriority 和 pollHighest

解题思路

这道题要求我们设计一个事件管理器，支持获取最高优先级事件和更新优先级操作。关键挑战是如何高效地处理优先级更新。

核心思路：

使用最大堆来维护事件，按优先级排序（优先级相同时按 eventId 升序）
使用哈希表记录每个事件的当前有效优先级
对于优先级更新，采用"懒删除"策略：不从堆中删除旧版本，而是直接插入新版本
在 pollHighest 时，持续弹出堆顶元素，直到找到一个有效的事件（堆中优先级与哈希表中记录一致）

具体实现：

堆中存储 {priority, -eventId} 对，负号确保 eventId 小的优先
哈希表 currentPriority 记录每个活跃事件的当前优先级
updatePriority 时直接更新哈希表并向堆中添加新记录
pollHighest 时循环弹出过期记录，直到找到有效事件

这种方法避免了从堆中删除元素的复杂操作，时间复杂度为 O(log n)，空间复杂度为 O(n)。

代码实现

class EventManager {
private:
    priority_queue<pair<int, int>> maxHeap; // {priority, -eventId}
    unordered_map<int, int> currentPriority; // eventId -> current priority
    
public:
    EventManager(vector<vector<int>>& events) {
        for (auto& event : events) {
            int eventId = event[0], priority = event[1];
            maxHeap.push({priority, -eventId});
            currentPriority[eventId] = priority;
        }
    }
    
    void updatePriority(int eventId, int newPriority) {
        currentPriority[eventId] = newPriority;
        maxHeap.push({newPriority, -eventId});
    }
    
    int pollHighest() {
        while (!maxHeap.empty()) {
            auto [priority, negEventId] = maxHeap.top();
            maxHeap.pop();
            int eventId = -negEventId;
            
            if (currentPriority.count(eventId) && currentPriority[eventId] == priority) {
                currentPriority.erase(eventId);
                return eventId;
            }
        }
        return -1;
    }
};

import heapq

class EventManager:
    def __init__(self, events: list[list[int]]):
        self.max_heap = []
        self.current_priority = {}
        
        for event_id, priority in events:
            heapq.heappush(self.max_heap, (-priority, event_id))
            self.current_priority[event_id] = priority
    
    def updatePriority(self, eventId: int, newPriority: int) -> None:
        self.current_priority[eventId] = newPriority
        heapq.heappush(self.max_heap, (-newPriority, eventId))
    
    def pollHighest(self) -> int:
        while self.max_heap:
            neg_priority, event_id = heapq.heappop(self.max_heap)
            priority = -neg_priority
            
            if event_id in self.current_priority and self.current_priority[event_id] == priority:
                del self.current_priority[event_id]
                return event_id
        
        return -1

public class EventManager {
    private PriorityQueue<(int priority, int eventId), (int, int)> maxHeap;
    private Dictionary<int, int> currentPriority;
    
    public EventManager(int[][] events) {
        maxHeap = new PriorityQueue<(int, int), (int, int)>(
            Comparer<(int, int)>.Create((a, b) => {
                if (a.Item1 != b.Item1) return b.Item1.CompareTo(a.Item1); // Max priority
                return a.Item2.CompareTo(b.Item2); // Min eventId
            })
        );
        currentPriority = new Dictionary<int, int>();
        
        foreach (var e in events) {
            int eventId = e[0], priority = e[1];
            maxHeap.Enqueue((priority, eventId), (priority, eventId));
            currentPriority[eventId] = priority;
        }
    }
    
    public void UpdatePriority(int eventId, int newPriority) {
        currentPriority[eventId] = newPriority;
        maxHeap.Enqueue((newPriority, eventId), (newPriority, eventId));
    }
    
    public int PollHighest() {
        while (maxHeap.Count > 0) {
            var (priority, eventId) = maxHeap.Dequeue();
            
            if (currentPriority.ContainsKey(eventId) && currentPriority[eventId] == priority) {
                currentPriority.Remove(eventId);
                return eventId;
            }
        }
        return -1;
    }
}

var EventManager = function(events) {
    this.events = new Map();
    for (let [eventId, priority] of events) {
        this.events.set(eventId, priority);
    }
};

EventManager.prototype.updatePriority = function(eventId, newPriority) {
    this.events.set(eventId, newPriority);
};

EventManager.prototype.pollHighest = function() {
    if (this.events.size === 0) return -1;
    
    let maxPriority = -1;
    let targetEventId = -1;
    
    for (let [eventId, priority] of this.events) {
        if (priority > maxPriority || (priority === maxPriority && eventId < targetEventId)) {
            maxPriority = priority;
            targetEventId = eventId;
        }
    }
    
    this.events.delete(targetEventId);
    return targetEventId;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

操作	时间复杂度	空间复杂度
初始化	O(n log n)	O(n)
updatePriority	O(log n)	O(1)
pollHighest	O(log n)	O(1)

其中 n 是事件的数量。虽然堆中可能存在过期的元素，但每个事件最多被更新有限次，总体复杂度仍然是高效的。

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析