题目描述

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

请你设计一个 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。

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

样例

输入：
["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 <= 10^5
• 0 <= userId <= 10^5
• 0 <= taskId <= 10^5
• 0 <= priority <= 10^9
• 0 <= newPriority <= 10^9
• add，edit，rmv 和 execTop 的总操作次数 加起来 不超过 2 * 10^5 次。

算法

(堆延迟删除，哈希表) 添加和修改 $O(\log n)$；删除和查询 $O(1)$。

1. 维护一个堆，键为任务的优先级。
2. 维护一个哈希表，键为任务 ID。
3. 增加和修改时，更新哈希表，并在堆中插入一条元素。
4. 删除时，从哈希表中删除。
5. 查询时，从堆顶弹出元素。如果堆顶元素不再哈希表中存在或优先级与哈希表中的优先级不匹配，则丢弃，再继续弹出下一个。最后将合法的元素从哈希表中删除。

时间复杂度

• 添加和修改需要往堆中添加元素，故时间复杂度为 $O(\log n)$。
• 删除只需要修改哈希表，时间复杂度为 $O(1)$。
• 查询均摊下来时间复杂度也为 $O(1)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储堆和哈希表。

C++ 代码

class TaskManager {
private:
    unordered_map<int, pair<int, int>> task_info;
    priority_queue<pair<int, pair<int, int>>> heap;

public:
    TaskManager(vector<vector<int>>& tasks) {
        for (const auto &t : tasks) {
            task_info[t[1]] = make_pair(t[2], t[0]);
            heap.push(make_pair(t[2], make_pair(t[1], t[0])));
        }
    }

    void add(int userId, int taskId, int priority) {
        task_info[taskId] = make_pair(priority, userId);
        heap.push(make_pair(priority, make_pair(taskId, userId)));
    }

    void edit(int taskId, int newPriority) {
        task_info[taskId].first = newPriority;
        heap.push(make_pair(newPriority, make_pair(taskId, task_info[taskId].second)));
    }

    void rmv(int taskId) {
        task_info.erase(taskId);
    }

    int execTop() {
        while (!heap.empty()) {
            auto top = heap.top();
            heap.pop();
            int taskId = top.second.first;
            int priority = top.first;

            if (task_info.find(taskId) != task_info.end() && 
                task_info[taskId].first == priority
            ) {
                task_info.erase(taskId);

                return top.second.second;
            }
        }

        return -1;
    }
};

/**
 * Your TaskManager object will be instantiated and called as such:
 * TaskManager* obj = new TaskManager(tasks);
 * obj->add(userId,taskId,priority);
 * obj->edit(taskId,newPriority);
 * obj->rmv(taskId);
 * int param_4 = obj->execTop();
 */