What is the primary data structure used in the Design Task Manager?

The primary data structures used in this problem are a Hash Table for storing tasks and a Heap (Priority Queue) for managing task priorities.

How do I efficiently manage task priorities in this problem?

To efficiently manage task priorities, use a heap to track the highest or lowest priority task and adjust the heap as tasks are added or priorities are updated.

What is the time complexity of each operation in the Task Manager?

The time complexity for adding, editing, and removing tasks is O(log n) due to heap operations, while accessing the hash table takes O(1) for most tasks.

How does the Task Manager handle edge cases such as empty task lists?

The system should handle edge cases by ensuring that it doesn't attempt to execute or remove tasks when no tasks are present in the system.

How can GhostInterview assist with solving this problem efficiently?

GhostInterview helps by guiding candidates through the use of appropriate data structures (hash table and heap) and explaining how to manage large inputs with optimal time complexity.

#3408

Medium

auto_awesome堆

LeetCode 题解工作台

设计任务管理器

一个任务管理器系统可以让用户管理他们的任务，每个任务有一个优先级。这个系统需要高效地处理添加、修改、执行和删除任务的操作。请你设计一个 TaskManager 类： TaskManager(vector >& tasks) 初始化任务管理器，初始化的数组格式为 [userId, taskId, p…

哈希表设计堆（优先队列）有序集合

题目描述

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

请你设计一个 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 <= 10⁵
0 <= userId <= 10⁵
0 <= taskId <= 10⁵
0 <= priority <= 10⁹
0 <= newPriority <= 10⁹
add ，edit ，rmv 和 execTop 的总操作次数 加起来 不超过 2 * 10⁵ 次。
输入保证 taskId 是合法的。

lightbulb

解题思路

方法一：哈希表 + 有序集合

我们用一个哈希表 $\text{d}$ 来存储任务信息，键为任务 ID，值为一个二元组 $(\text{userId}, \text{priority})$ ，表示该任务所属的用户 ID 以及任务的优先级。

我们用一个有序集合 $\text{st}$ 来存储当前系统中的所有任务，元素为一个二元组 $(-\text{priority}, -\text{taskId})$ ，表示任务的优先级和任务 ID 的相反数。我们将优先级和任务 ID 取相反数是为了让优先级最高且任务 ID 最大的任务在有序集合中排在最前面。

对于每个操作，我们可以按如下方式进行处理：

初始化：对于每个任务 $(\text{userId}, \text{taskId}, \text{priority})$ ，我们将其添加到哈希表 $\text{d}$ 和有序集合 $\text{st}$ 中。
添加任务：将任务 $(\text{userId}, \text{taskId}, \text{priority})$ 添加到哈希表 $\text{d}$ 和有序集合 $\text{st}$ 中。
编辑任务：从哈希表 $\text{d}$ 中获取任务 ID 对应的用户 ID 和旧优先级，然后从有序集合 $\text{st}$ 中删除旧的任务信息，再将新的任务信息添加到哈希表 $\text{d}$ 和有序集合 $\text{st}$ 中。
删除任务：从哈希表 $\text{d}$ 中获取任务 ID 对应的优先级，然后从有序集合 $\text{st}$ 中删除任务信息，并从哈希表 $\text{d}$ 中删除任务。
执行最高优先级任务：如果有序集合 $\text{st}$ 为空，返回 -1。否则，从有序集合 $\text{st}$ 中取出第一个元素，获取任务 ID，然后从哈希表 $\text{d}$ 中获取对应的用户 ID，并将任务从哈希表 $\text{d}$ 和有序集合 $\text{st}$ 中删除，最后返回用户 ID。

时间复杂度方面，初始化操作需要 $O(n \log n)$ 的时间，其中 $n$ 是初始任务的数量。每个添加、编辑、删除和执行操作都需要 $O(\log m)$ 的时间，其中 $m$ 是当前系统中的任务数量。由于总操作次数不超过 $2 \times 10^5$ ，因此整体时间复杂度是可接受的。空间复杂度 $O(n + m)$ ，用于存储哈希表和有序集合。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

class TaskManager:

    def __init__(self, tasks: List[List[int]]):
        self.d = {}
        self.st = SortedList()
        for task in tasks:
            self.add(*task)

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

    def edit(self, taskId: int, newPriority: int) -> None:
        userId, priority = self.d[taskId]
        self.st.discard((-priority, -taskId))
        self.d[taskId] = (userId, newPriority)
        self.st.add((-newPriority, -taskId))

    def rmv(self, taskId: int) -> None:
        _, priority = self.d[taskId]
        self.d.pop(taskId)
        self.st.remove((-priority, -taskId))

    def execTop(self) -> int:
        if not self.st:
            return -1
        taskId = -self.st.pop(0)[1]
        userId, _ = self.d[taskId]
        self.d.pop(taskId)
        return userId


# Your TaskManager object will be instantiated and called as such:
# obj = TaskManager(tasks)
# obj.add(userId,taskId,priority)
# obj.edit(taskId,newPriority)
# obj.rmv(taskId)
# param_4 = obj.execTop()

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Understanding how to combine a hash table for storage and a heap for priority management will be crucial.
question_mark
The candidate should be able to explain how the operations affect the time complexity.
question_mark
Efficient memory management while performing these operations should be discussed, especially with large inputs.

warning

常见陷阱

外企场景

error
Failing to update the heap properly when task priorities change can lead to incorrect execution order.
error
Not considering edge cases such as executing or removing tasks from an empty system.
error
Overcomplicating the data structures or operations instead of using a simple Hash Table and Heap combination.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Implementing a Task Manager that handles multiple users with different priorities for tasks.
arrow_right_alt
Expanding the system to support additional operations such as querying the number of tasks left with certain priorities.
arrow_right_alt
Optimizing the Task Manager to handle larger datasets with reduced time complexity for each operation.

help

常见问题

外企场景

继续练习

#2424 最长上传前缀 #2353 设计食物评分系统 #2349 设计数字容器系统