Design Task Manager

main.md

Question

Approach

I keep a global max-heap of tasks keyed by (-priority, -taskId) so the highest priority (and, on ties, the largest taskId) is on top. I also maintain a hashmap info[taskId] = (userId, priority) as the source of truth. All updates are done by lazy heap updates: on add or edit I push a fresh heap entry; on rmv I delete from the map. In execTop, I pop heap entries until I find one that still matches the current mapping (i.e., taskId exists and priority matches); then I remove it from the map and return its userId. If the heap runs out, I return -1.

Implementation

class TaskManager:

    def __init__(self, tasks: List[List[int]]):
        self.info: Dict[int, Tuple[int, int]] = {}
        self.heap: List[Tuple[int, int, int]] = []
        for userId, taskId, priority in tasks:
            self.info[taskId] = (userId, priority)
            heapq.heappush(self.heap, (-priority, -taskId, taskId))

    def add(self, userId: int, taskId: int, priority: int) -> None:
        self.info[taskId] = (userId, priority)
        heapq.heappush(self.heap, (-priority, -taskId, taskId))

    def edit(self, taskId: int, newPriority: int) -> None:
        userId, _ = self.info[taskId]
        self.info[taskId] = (userId, newPriority)
        heapq.heappush(self.heap, (-newPriority, -taskId, taskId))

    def rmv(self, taskId: int) -> None:
        if taskId in self.info:
            del self.info[taskId]

    def execTop(self) -> int:
        while self.heap:
            negP, negTid, tid = heapq.heappop(self.heap)
            if tid not in self.info:
                continue
            userId, curP = self.info[tid]
            if -negP != curP:
                continue
            del self.info[tid]
            return userId
        return -1

Complexities

• Time: O(log n)
• Space: O(n)