题目

一个任务管理器系统可以让用户管理他们的任务，每个任务有一个优先级。这个系统需要高效地处理添加、修改、执行和删除任务的操作。

请你设计一个 TaskManager 类：

TaskManager(vector<vector<int>>& tasks) 初始化任务管理器，初始化的数组格式为 [userId, taskId, priority] ，表示给 userId 添加一个优先级为 priority 的任务 taskId 。
void add(int userId, int taskId, int priority) 表示给用户 userId 添加一个优先级为 priority 的任务 taskId ，输入保证 taskId 不在系统中。
void edit(int taskId, int newPriority) 更新已经存在的任务 taskId 的优先级为 newPriority 。输入保证 taskId 存在于系统中。
void rmv(int taskId) 从系统中删除任务 taskId 。输入保证 taskId 存在于系统中。
int execTop() 执行所有用户的任务中优先级最高的任务，如果有多个任务优先级相同且都为最高，执行 taskId 最大的一个任务。执行完任务后，taskId 从系统中删除。同时请你返回这个任务所属的用户 userId 。如果不存在任何任务，返回 -1 。

注意，一个用户可能被安排多个任务。

示例 1：

输入： [“TaskManager”, “add”, “edit”, “execTop”, “rmv”, “add”, “execTop”] [[[[1, 101, 10], [2, 102, 20], [3, 103, 15]]], [4, 104, 5], [102, 8], [], [101], [5, 105, 15], []]

输出： [null, null, null, 3, null, null, 5]

解释：

TaskManager taskManager = new TaskManager([[1, 101, 10], [2, 102, 20], [3, 103, 15]]); // 分别给用户 1 ，2 和 3 初始化一个任务。 taskManager.add(4, 104, 5); // 给用户 4 添加优先级为 5 的任务 104 。 taskManager.edit(102, 8); // 更新任务 102 的优先级为 8 。 taskManager.execTop(); // 返回 3 。执行用户 3 的任务 103 。 taskManager.rmv(101); // 将系统中的任务 101 删除。 taskManager.add(5, 105, 15); // 给用户 5 添加优先级为 15 的任务 105 。 taskManager.execTop(); // 返回 5 。执行用户 5 的任务 105 。

提示：

1 <= tasks.length <= 105
0 <= userId <= 105
0 <= taskId <= 105
0 <= priority <= 109
0 <= newPriority <= 109
add ，edit ，rmv 和 execTop 的总操作次数 加起来 不超过 2 * 10^5 次。
输入保证 taskId 是合法的。

解题思路

这个问题的核心在于，我们需要同时满足两种看似矛盾的需求：

快速随机访问/修改：edit 和 rmv 操作需要根据 taskId 快速定位到某个任务。这种操作最适合的数据结构是哈希表（Hash Map / Dictionary）。
快速找到并移除最大值：execTop 操作需要高效地在所有任务中找到“最优”任务（优先级最高，同优先级下 taskId 最大），然后删除它。这种操作是优先队列（Priority Queue） 的经典应用场景，通常用堆（Heap） 来实现。

如果只用哈希表，execTop 就需要遍历所有任务，时间复杂度为 $O(N)$，在 $N$ 很大时效率太低。如果只用堆，edit 和 rmv 就需要先在堆中找到指定的 taskId，这也是一个 $O(N)$ 的操作，同样无法接受。

因此，正确的解题思路是将这两种数据结构结合起来。

哈希表 + 优先队列（堆）

我们将使用两种数据结构来共同维护任务的状态：

一个哈希表 tasks：
- 键（Key）: taskId
- 值（Value）: [userId, priority]
- 作用: 实现 O(1) 时间复杂度的任务查找、修改和删除。通过 taskId 可以立刻获得其所属的 userId和当前的 priority。
一个最大堆（Max-Heap）pq (Priority Queue)：
- 存储内容: (priority, taskId) 的元组（Tuple）。
- 排序规则: 默认按元组的第一个元素（priority）进行比较，如果第一个元素相同，则比较第二个元素（taskId）。这完美符合题目“优先级最高，taskId最大”的要求。
- 作用: 实现 O(log N) 时间复杂度的“最优”任务查找和移除。堆顶永远是当前系统中的最优任务。
- 实现注意: Python 的 heapq 模块实现的是最小堆。为了模拟最大堆，我们可以在存入数据时对 priority 和 taskId 都取负数。这样，priority 最大的任务其负数就最小，taskId 最大的任务其负数也最小，正好可以利用最小堆来找到它们。

如何同步哈希表和堆？

add 和 execTop 比较直接，但 edit 和 rmv 会带来一个问题：如何在修改/删除哈希表中的一个任务后，同步更新它在堆中的状态？

直接在堆中找到并删除/修改一个非堆顶的元素，时间复杂度是 O(N)，这又回到了最初的性能瓶 chiffres。

这里的关键技巧是采用 “懒删除”（Lazy Deletion） 策略。

懒删除策略

我们不真正地从堆里删除旧的、无效的条目。而是：

对于 rmv(taskId): 我们只在哈希表 tasks 中删除该任务。堆中那个关于 taskId 的 (priority, taskId)元组就成了一个“僵尸”条目。
对于 edit(taskId, newPriority): 我们在哈希表 tasks 中更新任务的优先级，然后向堆中插入一个新的 (-newPriority, -taskId) 元组。此时，堆中就有了两个关于此 taskId 的条目：一个是旧的（现在是“僵尸”条目），一个是新的。

那么，如何处理这些“僵尸”条目呢？答案是在 execTop 时进行验证。

当 execTop 从堆顶取出一个 (-p, -t) 任务时，我们必须检查它是否有效：

检查任务是否存在：去哈希表 tasks 中查找 t。如果 t 不在哈希表中，说明这个任务已经被 rmv 操作删除了。这是一个“僵尸”条目，应该丢弃，然后继续从堆中取下一个。
检查任务是否是最新版本：如果 t 存在于哈希表 tasks 中，我们还需要比较它的优先级。从堆中取出的优先级是 p，而去哈希表中查到的当前优先级是 tasks[t][1]。如果 p != tasks[t][1]，说明这个任务已经被 edit 操作更新过了，堆里的这个是旧版本的“僵尸”条目。同样，丢弃它，继续取下一个。

只有当一个从堆顶取出的任务同时存在于哈希表且优先级匹配时，它才是我们真正要找的、有效的最优任务。

各个方法实现逻辑

TaskManager(tasks) (初始化):
1. 创建空的哈希表 self.tasks 和空的堆 self.pq。
2. 遍历输入的 tasks 数组，对每个 [userId, taskId, priority] 调用 add 方法，复用逻辑。
add(userId, taskId, priority):
1. 在哈希表中添加映射：self.tasks[taskId] = [userId, priority]。
2. 向堆中推入新元素：heapq.heappush(self.pq, (-priority, -taskId))。
- 时间复杂度: O(log N)
edit(taskId, newPriority):
1. 从哈希表 self.tasks 中获取 userId。
2. 更新哈希表中的优先级：self.tasks[taskId][1] = newPriority。
3. 向堆中推入更新后的元素：heapq.heappush(self.pq, (-newPriority, -taskId))。旧的条目留在堆中，成为“僵尸”。
- 时间复杂度: O(log N)
rmv(taskId):
1. 从哈希表中删除任务：del self.tasks[taskId]。旧的条目留在堆中，成为“僵尸”。
- 时间复杂度: O(1)
execTop():
1. 进入一个循环，只要堆不为空就继续。
2. 从堆顶弹出一个元素 (-priority, -taskId)。
3. 验证：
  - 检查 taskId 是否在 self.tasks 中。
  - 如果存在，再检查 self.tasks[taskId][1] 是否等于 priority。
4. 如果验证失败，说明是“僵尸”条目，continue 循环，处理下一个堆顶元素。
5. 如果验证成功，说明找到了真正的最优任务。
  - 从 self.tasks 中获取 userId。
  - 执行任务（即删除它）：del self.tasks[taskId]。
  - 返回 userId。
6. 如果循环结束（堆变空了）还没找到有效任务，说明没有任务了，返回 -1。
- 时间复杂度: 摊销后为 O(log N)。虽然 while 循环可能执行多次，但每个任务最多只会被成功弹出一次。那些被丢弃的“僵尸”条目的总数不会超过操作总数，因此总的开销被分摊了。

操作	数据结构选择	时间复杂度	关键点
`add`	哈希表 `put`，堆 `push`	$O(log N)$	同时更新两者
`edit`	哈希表 `put`，堆 `push`	$O(log N)$	懒删除：只添加新条目到堆
`rmv`	哈希表 `remove`	$O(1)$	懒删除：只操作哈希表
`execTop`	堆 `pop`，哈希表 `get` & `remove`	$O(log N)$ (摊销)	循环验证堆顶元素的有效性

具体代码

// 为了方便，定义一个类型别名来表示优先队列中的元素
// pair 的第一个元素是 priority，第二个是 taskId
// C++ 的 priority_queue 默认是最大堆，且 pair 会先比较 first 再比较 second，
// 这完全符合题目的要求。
using TaskPair = std::pair<int, int>;

class TaskManager {
private:
    // 哈希表：taskId -> {userId, priority}
    // 用于 O(1) 查找任务信息
    std::unordered_map<int, std::pair<int, int>> task_map;

    // 最大堆（优先队列）
    // 存储 {priority, taskId} 对，堆顶永远是当前最优任务
    std::priority_queue<TaskPair> pq;

public:
    // 构造函数
    TaskManager(std::vector<std::vector<int>>& tasks) {
        // 遍历初始任务列表，调用 add 方法来初始化
        for (const auto& task : tasks) {
            add(task[0], task[1], task[2]);
        }
    }
    
    // 添加任务
    void add(int userId, int taskId, int priority) {
        // 在哈希表中记录任务信息
        task_map[taskId] = {userId, priority};
        // 将新任务推入优先队列
        pq.push({priority, taskId});
    }
    
    // 编辑任务
    void edit(int taskId, int newPriority) {
        // 更新哈希表中的优先级
        // 注意：task_map[taskId] 会返回一个引用，可以直接修改其成员
        task_map[taskId].second = newPriority;
        // 【懒删除策略】将更新后的任务推入优先队列
        // 此时，旧的 {oldPriority, taskId} 条目仍然留在队列中，变成了“僵尸”条目
        pq.push({newPriority, taskId});
    }
    
    // 删除任务
    void rmv(int taskId) {
        // 【懒删除策略】只从哈希表中移除任务
        // 队列中对应的条目也变成了“僵尸”条目
        task_map.erase(taskId);
    }
    
    // 执行最优任务
    int execTop() {
        // 循环直到找到一个有效的任务或队列为空
        while (!pq.empty()) {
            // 获取当前堆顶的最优任务
            TaskPair top_task = pq.top();
            pq.pop(); // 无论如何都先弹出

            int priority = top_task.first;
            int taskId = top_task.second;

            // 【验证有效性】
            // 1. 检查任务是否已被删除 (rmv)
            //    如果 task_map.count(taskId) == 0，说明任务不存在，是僵尸条目
            // 2. 检查任务是否是最新版本 (edit)
            //    如果 task_map[taskId].second != priority，说明这是一个旧版本的僵尸条目
            if (task_map.count(taskId) && task_map[taskId].second == priority) {
                // 验证通过，这是当前真正的最优任务
                int userId = task_map[taskId].first;
                
                // 执行任务，即从系统中删除
                task_map.erase(taskId);
                
                return userId;
            }
            
            // 如果验证失败，则当前 top_task 是一个“僵尸”条目，循环继续，处理下一个堆顶元素
        }

        // 如果队列为空还没找到有效任务，说明没有任务了
        return -1;
    }
};

beautifulremi / 3408. 设计任务管理器