3408. 设计任务管理器

Medium

题目描述

有一个任务管理系统，允许用户管理他们的任务，每个任务都有关联的优先级。系统应该能够高效地处理添加、修改、执行和删除任务。

实现 TaskManager 类：

TaskManager(vector<vector<int>>& tasks) 用用户-任务-优先级三元组列表初始化任务管理器。输入列表中的每个元素的形式为 [userId, taskId, priority]，将具有给定优先级的任务添加到指定用户。
void add(int userId, int taskId, int priority) 将具有指定 taskId 和优先级的任务添加到 userId 用户。保证 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 <= 10^5
0 <= userId <= 10^5
0 <= taskId <= 10^5
0 <= priority <= 10^9
0 <= newPriority <= 10^9
总共最多调用 2 * 10^5 次 add、edit、rmv 和 execTop 方法
输入保证 taskId 是有效的

解题思路

这道题要求我们设计一个任务管理器，核心是需要高效地维护任务的优先级顺序，并支持动态的增删改查操作。

解题思路分析：

主要挑战在于 execTop() 操作需要快速找到优先级最高的任务（相同优先级时选择 taskId 最大的），这提示我们需要使用能够维护有序性的数据结构。

方案选择：

哈希表 + 优先队列：使用哈希表存储 taskId 到任务信息的映射，使用优先队列维护任务顺序。但优先队列的删除和修改操作效率较低。
哈希表 + 有序集合（推荐）：使用哈希表快速定位任务，使用有序集合（如 C++ 的 set）维护按优先级和 taskId 排序的任务。这样所有操作都能在 O(log n) 时间内完成。

实现细节：

使用哈希表 taskInfo 存储 taskId 到 (userId, priority) 的映射
使用有序集合 orderedTasks 存储 (priority, taskId) 对，按优先级降序、taskId 降序排列
add 操作：在两个数据结构中都添加相应信息
edit 操作：先从有序集合中删除旧的 (priority, taskId)，更新优先级后重新插入
rmv 操作：从两个数据结构中都删除相应信息
execTop 操作：从有序集合的最大元素开始执行并删除

代码实现

class TaskManager {
private:
    unordered_map<int, pair<int, int>> taskInfo; // taskId -> {userId, priority}
    set<pair<int, int>, greater<pair<int, int>>> orderedTasks; // {priority, taskId} ordered by priority desc, taskId desc
    
public:
    TaskManager(vector<vector<int>>& tasks) {
        for (auto& task : tasks) {
            int userId = task[0], taskId = task[1], priority = task[2];
            add(userId, taskId, priority);
        }
    }
    
    void add(int userId, int taskId, int priority) {
        taskInfo[taskId] = {userId, priority};
        orderedTasks.insert({priority, taskId});
    }
    
    void edit(int taskId, int newPriority) {
        int oldPriority = taskInfo[taskId].second;
        orderedTasks.erase({oldPriority, taskId});
        taskInfo[taskId].second = newPriority;
        orderedTasks.insert({newPriority, taskId});
    }
    
    void rmv(int taskId) {
        int priority = taskInfo[taskId].second;
        orderedTasks.erase({priority, taskId});
        taskInfo.erase(taskId);
    }
    
    int execTop() {
        if (orderedTasks.empty()) {
            return -1;
        }
        
        auto it = orderedTasks.begin();
        int priority = it->first, taskId = it->second;
        int userId = taskInfo[taskId].first;
        
        orderedTasks.erase(it);
        taskInfo.erase(taskId);
        
        return userId;
    }
};

from sortedcontainers import SortedSet

class TaskManager:
    def __init__(self, tasks: List[List[int]]):
        self.task_info = {}  # taskId -> (userId, priority)
        self.ordered_tasks = SortedSet(key=lambda x: (-x[0], -x[1]))  # (priority, taskId) sorted desc
        
        for userId, taskId, priority in tasks:
            self.add(userId, taskId, priority)

    def add(self, userId: int, taskId: int, priority: int) -> None:
        self.task_info[taskId] = (userId, priority)
        self.ordered_tasks.add((priority, taskId))

    def edit(self, taskId: int, newPriority: int) -> None:
        userId, oldPriority = self.task_info[taskId]
        self.ordered_tasks.remove((oldPriority, taskId))
        self.task_info[taskId] = (userId, newPriority)
        self.ordered_tasks.add((newPriority, taskId))

    def rmv(self, taskId: int) -> None:
        userId, priority = self.task_info[taskId]
        self.ordered_tasks.remove((priority, taskId))
        del self.task_info[taskId]

    def execTop(self) -> int:
        if not self.ordered_tasks:
            return -1
        
        priority, taskId = self.ordered_tasks.pop(0)
        userId = self.task_info[taskId][0]
        del self.task_info[taskId]
        
        return userId

public class TaskManager {
    private Dictionary<int, (int userId, int priority)> taskInfo;
    private SortedSet<(int priority, int taskId)> orderedTasks;
    
    public TaskManager(IList<IList<int>> tasks) {
        taskInfo = new Dictionary<int, (int, int)>();
        orderedTasks = new SortedSet<(int, int)>(new TaskComparer());
        
        foreach (var task in tasks) {
            Add(task[0], task[1], task[2]);
        }
    }
    
    public void Add(int userId, int taskId, int priority) {
        taskInfo[taskId] = (userId, priority);
        orderedTasks.Add((priority, taskId));
    }
    
    public void Edit(int taskId, int newPriority) {
        var (userId, oldPriority) = taskInfo[taskId];
        orderedTasks.Remove((oldPriority, taskId));
        taskInfo[taskId] = (userId, newPriority);
        orderedTasks.Add((newPriority, taskId));
    }
    
    public void Rmv(int taskId) {
        var (userId, priority) = taskInfo[taskId];
        orderedTasks.Remove((priority, taskId));
        taskInfo.Remove(taskId);
    }
    
    public int ExecTop() {
        if (orderedTasks.Count == 0) {
            return -1;
        }
        
        var maxTask = orderedTasks.Max;
        int priority = maxTask.priority, taskId = maxTask.taskId;
        int userId = taskInfo[taskId].userId;
        
        orderedTasks.Remove(maxTask);
        taskInfo.Remove(taskId);
        
        return userId;
    }
    
    private class TaskComparer : IComparer<(int priority, int taskId)> {
        public int Compare((int priority, int taskId) x, (int priority, int taskId) y) {
            if (x.priority != y.priority) {
                return x.priority.CompareTo(y.priority);
            }
            return x.taskId.CompareTo(y.taskId);
        }
    }
}

var TaskManager = function(tasks) {
    this.taskMap = new Map(); // taskId -> {userId, priority}
    this.priorityMap = new Map(); // priority -> Map(taskId -> userId)
    this.maxPriority = -1;
    
    for (let [userId, taskId, priority] of tasks) {
        this.add(userId, taskId, priority);
    }
};

TaskManager.prototype.add = function(userId, taskId, priority) {
    this.taskMap.set(taskId, {userId, priority});
    
    if (!this.priorityMap.has(priority)) {
        this.priorityMap.set(priority, new Map());
    }
    this.priorityMap.get(priority).set(taskId, userId);
    
    this.maxPriority = Math.max(this.maxPriority, priority);
};

TaskManager.prototype.edit = function(taskId, newPriority) {
    const task = this.taskMap.get(taskId);
    const oldPriority = task.priority;
    const userId = task.userId;
    
    // Remove from old priority
    this.priorityMap.get(oldPriority).delete(taskId);
    if (this.priorityMap.get(oldPriority).size === 0) {
        this.priorityMap.delete(oldPriority);
        if (oldPriority === this.maxPriority) {
            this.updateMaxPriority();
        }
    }
    
    // Add to new priority
    task.priority = newPriority;
    if (!this.priorityMap.has(newPriority)) {
        this.priorityMap.set(newPriority, new Map());
    }
    this.priorityMap.get(newPriority).set(taskId, userId);
    
    this.maxPriority = Math.max(this.maxPriority, newPriority);
};

TaskManager.prototype.rmv = function(taskId) {
    const task = this.taskMap.get(taskId);
    const priority = task.priority;
    
    this.taskMap.delete(taskId);
    this.priorityMap.get(priority).delete(taskId);
    
    if (this.priorityMap.get(priority).size === 0) {
        this.priorityMap.delete(priority);
        if (priority === this.maxPriority) {
            this.updateMaxPriority();
        }
    }
};

TaskManager.prototype.execTop = function() {
    if (this.maxPriority === -1) return -1;
    
    const tasksAtMaxPriority = this.priorityMap.get(this.maxPriority);
    let maxTaskId = -1;
    let userId = -1;
    
    for (let [taskId, uid] of tasksAtMaxPriority) {
        if (taskId > maxTaskId) {
            maxTaskId = taskId;
            userId = uid;
        }
    }
    
    this.rmv(maxTaskId);
    return userId;
};

TaskManager.prototype.updateMaxPriority = function() {
    this.maxPriority = -1;
    for (let priority of this.priorityMap.keys()) {
        this.maxPriority = Math.max(this.maxPriority, priority);
    }
};

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

复杂度分析

操作	时间复杂度	空间复杂度
构造函数	O(n log n)	O(n)
add	O(log n)	O(1)
edit	O(log n)	O(1)
rmv	O(log n)	O(1)
execTop	O(log n)	O(1)

其中 n 是系统中的任务总数。使用有序集合保证了所有操作的对数时间复杂度，空间复杂度为 O(n) 用于存储任务信息。

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析