Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The manager needs two views of the same tasks: direct lookup by task ID for edits and removals, and priority order for execution. An information map plus an ordered collection provides both without scanning all tasks.

Approach

Store active tasks as (priority, taskId, userId) entries in the ordered collection, and map each task ID to its priority and owner. The largest ordered entry has the highest priority, breaking ties by the larger task ID; unique task IDs make the final user field irrelevant to tie-breaking.

Adding inserts into both structures. Editing looks up and removes the old ordered entry, inserts the replacement priority, and updates the map. Removing deletes the ordered entry and its map record. Executing returns -1 if the ordered collection is empty; otherwise it removes its largest entry and returns that entry's user ID.

The ordered collection determines which tasks are active. In the supplied implementation, execution leaves the information-map record behind, so the memory analysis accounts for retained task IDs rather than only currently active tasks.

class TaskManager:
    def __init__(self, tasks: List[List[int]]):
        self.sl = SortedList()
        self.task_info = {}
        for u, t, p in tasks:
            self.sl.add((p, t, u))
            self.task_info[t] = (p, u)

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

    def edit(self, taskId: int, newPriority: int) -> None:
        old_p, u = self.task_info[taskId]
        self.sl.discard((old_p, taskId, u))
        self.sl.add((newPriority, taskId, u))
        self.task_info[taskId] = (newPriority, u)

    def rmv(self, taskId: int) -> None:
        old_p, u = self.task_info[taskId]
        self.sl.discard((old_p, taskId, u))
        del self.task_info[taskId]

    def execTop(self) -> int:
        if not self.sl:
            return -1
        old_p, old_t, u = self.sl[-1]
        self.sl.pop(-1)
        return u

Complexity analysis

Let A be the initial task count, N the current active count and D the number of task IDs retained in the information map. JavaScript's AVL collection gives O(A log(A + 1)) construction and O(log(N + 2)) ordered work per add, edit, rmv or nonempty execTop; map accesses are expected constant-time. Python's block-based SortedList has approximately logarithmic updates in practice, not strict worst-case logarithmic guarantees. Conservative Python bounds are O(A^2) construction and O(N + 1) per update/removal, allowing block shifts and merges. Empty execTop is O(1) in both versions. Persistent space is O(N + D): execution removes only the ordered entry, while explicit rmv deletes its map record; re-adding an executed ID overwrites the retained record.