3408. 设计任务管理器（Rating 1806）

以下内容偏向于记录个人练习过程及思考，请审慎阅读。

题目

3408. 设计任务管理器

Rating 1806

思路

维护以下三个数据结构即可

• 维护一个dict，记录taskId -> userId的映射关系
• 维护一个dict，记录taskId -> priority的映射关系
• 维护一个SortedSet，维护(priority, taskId)
  • （这里参考题解，也可以用普通有序list/优先队列/最大堆做懒更新，pop的时候跟最新的记录对一下就行，如果对不上说明这个记录已经被动过了，继续遍历即可）

代码

class TaskManager:
    def __init__(self, tasks: List[List[int]]):
        self.t2u = dict() # 维护一个dict，记录taskId -> userId的映射关系
        self.t2p = dict() # 维护一个dict，记录taskId -> priority的映射关系
        self.sst = SortedSet() # 维护一个SortedSet，维护(priority, taskId)
        for userId, taskId, priority in tasks:
            self.t2u[taskId] = userId
            self.t2p[taskId] = priority
            self.sst.add((priority, taskId))


    def add(self, userId: int, taskId: int, priority: int) -> None:
        self.t2u[taskId] = userId
        self.t2p[taskId] = priority
        self.sst.add((priority, taskId))        


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

    def rmv(self, taskId: int) -> None:
        del self.t2u[taskId]
        priority = self.t2p[taskId]
        del self.t2p[taskId]
        self.sst.remove((priority, taskId))
        

    def execTop(self) -> int:
        if not self.sst:
            return -1
        priority, taskId = self.sst[-1]
        userId = self.t2u[taskId]
        self.rmv(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()