Problem statement

A task manager tracks tasks that belong to users. Every task has a unique taskId, the userId it belongs to and a priority. Write the class TaskManager:

• TaskManager(int[][] tasks) starts with the given tasks; each tasks[i] is [userId, taskId, priority].
• void add(int userId, int taskId, int priority) adds a task for that user. No current task has this taskId.
• void edit(int taskId, int newPriority) changes the priority of an existing task.
• void rmv(int taskId) removes an existing task.
• int execTop() runs the task with the highest priority — among equal priorities, the one with the highest taskId — removes it from the manager and returns its userId. If there are no tasks it returns -1.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input: ["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],[]]
Output: [null,null,null,3,null,null,5]
Explanation: Task 102 drops from 20 to 8, so the top task is 103 (priority 15) of user 3. After 101 is removed, tasks 105 (15) and 104 (5) and 102 (8) remain; 105 runs, belonging to user 5.

Example 2

Input: ["TaskManager","execTop","execTop","add","execTop","execTop"]
[[[[7,3,0],[8,9,0]]],[],[],[6,3,1000000000],[],[]]
Output: [null,8,7,null,6,-1]
Explanation: Both tasks have priority 0, so the higher id 9 runs first (user 8), then 3 (user 7). Once task id 3 is free it can be added again; it runs, and then the manager is empty.

Constraints

• 1 <= tasks.length <= 10^5
• 0 <= userId <= 10^5
• 0 <= taskId <= 10^5
• 0 <= priority, newPriority <= 10^9
• At most 2 * 10^5 calls are made in total to add, edit, rmv and execTop
• add is only called with a taskId that is not currently in the manager; edit and rmv only with one that is

Hints for Design Task Manager

1. Hint 1

   Scanning every task in execTop is O(n) per call — too slow for 2 * 10^5 calls on 10^5 tasks.

2. Hint 2

   Order the tasks by the pair (priority, taskId) — both descending — in a max-heap or an ordered set, and keep a map from taskId to its user and current priority.

3. Hint 3

   With an ordered set, edit and rmv delete the old pair. With a heap, push the new pair on edit, leave old pairs in, and have execTop discard tops that no longer match the map (lazy deletion).

How to solve Design Task Manager

A map taskId → (userId, priority) holds the truth; a max-heap of (priority, taskId) pairs finds the top task. Changed and removed tasks leave stale pairs in the heap, which execTop recognises against the map and throws away.

Approach

1. For every initial task and every add, record it in the map and push (priority, taskId).
2. edit(taskId, p): update the map's priority and push (p, taskId); the old pair goes stale.
3. rmv(taskId): delete it from the map; its pairs go stale.
4. execTop(): pop pairs while the top's task is missing from the map or has a different priority there. If the heap empties, return -1; otherwise delete that task from the map, pop it and return its user.

Why it works

Every live task always has a heap pair equal to its current (priority, taskId), because each change pushes one. A pair that matches the map is therefore exactly a live task, and the heap orders pairs by priority, then id — so the first matching top is the task the problem asks for. Discarded pairs never match again unless the same (priority, taskId) comes back, in which case the pair is correct again.

Complexity

• Time — O(log n) amortised per call; O(n log n) to build
• Space — O(n + number of edits)

Pitfalls

• The tie-break is the higher taskId, not the lower one.
• A task removed and later re-added with the same id must not be confused with its old self — compare the priority stored in the map, not just the id.
• Pack (priority, taskId) into one 64-bit key (priority * 2^17 + taskId), or compare pairs; 32 bits are not enough.

Reference solution

Python

import heapq

class TaskManager:

    def __init__(self, tasks: List[List[int]]):
        self.info = {}  # taskId -> (userId, priority)
        self.heap = []  # (-priority, -taskId); stale pairs are skipped later
        for u, t, p in tasks:
            self.info[t] = (u, p)
            self.heap.append((-p, -t))
        heapq.heapify(self.heap)

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

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

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

    def execTop(self) -> int:
        while self.heap:
            p, t = self.heap[0]
            cur = self.info.get(-t)
            heapq.heappop(self.heap)
            if cur is not None and cur[1] == -p:
                del self.info[-t]
                return cur[0]
        return -1

Java

class TaskManager {
    private HashMap<Integer, Integer> user = new HashMap<>(), prio = new HashMap<>();
    private TreeSet<Long> order = new TreeSet<>(); // priority * 2^17 + taskId

    private static long key(int priority, int taskId) { return ((long) priority << 17) | taskId; }

    public TaskManager(int[][] tasks) {
        for (int[] t : tasks) add(t[0], t[1], t[2]);
    }

    public void add(int userId, int taskId, int priority) {
        user.put(taskId, userId);
        prio.put(taskId, priority);
        order.add(key(priority, taskId));
    }

    public void edit(int taskId, int newPriority) {
        order.remove(key(prio.get(taskId), taskId));
        prio.put(taskId, newPriority);
        order.add(key(newPriority, taskId));
    }

    public void rmv(int taskId) {
        order.remove(key(prio.get(taskId), taskId));
        prio.remove(taskId);
        user.remove(taskId);
    }

    public int execTop() {
        if (order.isEmpty()) return -1;
        int taskId = (int) (order.last() & ((1 << 17) - 1));
        int u = user.get(taskId);
        rmv(taskId);
        return u;
    }
}

C++

class TaskManager {
    unordered_map<int, int> user, prio; // taskId -> userId / current priority
    set<pair<int, int>> order;          // (priority, taskId)
public:
    TaskManager(vector<vector<int>>& tasks) {
        for (auto& t : tasks) add(t[0], t[1], t[2]);
    }

    void add(int userId, int taskId, int priority) {
        user[taskId] = userId;
        prio[taskId] = priority;
        order.insert({priority, taskId});
    }

    void edit(int taskId, int newPriority) {
        order.erase({prio[taskId], taskId});
        prio[taskId] = newPriority;
        order.insert({newPriority, taskId});
    }

    void rmv(int taskId) {
        order.erase({prio[taskId], taskId});
        prio.erase(taskId);
        user.erase(taskId);
    }

    int execTop() {
        if (order.empty()) return -1;
        int taskId = prev(order.end())->second;
        int u = user[taskId];
        rmv(taskId);
        return u;
    }
};

JavaScript

// A max-heap of packed keys priority * 2^17 + taskId (below 2^47, exact in a double).
var TM_SHIFT = 131072;

var TaskManager = function(tasks) {
    this.user = new Map(); // taskId -> userId
    this.prio = new Map(); // taskId -> current priority
    this.heap = [];        // stale keys are skipped by execTop
    for (var i = 0; i < tasks.length; i++) this.add(tasks[i][0], tasks[i][1], tasks[i][2]);
};

TaskManager.prototype.push = function(key) {
    var h = this.heap, i = h.length;
    h.push(key);
    while (i > 0) {
        var p = (i - 1) >> 1;
        if (h[p] >= key) break;
        h[i] = h[p]; i = p;
    }
    h[i] = key;
};

TaskManager.prototype.pop = function() {
    var h = this.heap, last = h.pop();
    if (h.length === 0) return;
    var i = 0, n = h.length;
    for (;;) {
        var l = 2 * i + 1, r = l + 1, m = i, mv = last;
        if (l < n && h[l] > mv) { m = l; mv = h[l]; }
        if (r < n && h[r] > mv) { m = r; mv = h[r]; }
        if (m === i) break;
        h[i] = h[m]; i = m;
    }
    h[i] = last;
};

TaskManager.prototype.add = function(userId, taskId, priority) {
    this.user.set(taskId, userId);
    this.prio.set(taskId, priority);
    this.push(priority * TM_SHIFT + taskId);
};

TaskManager.prototype.edit = function(taskId, newPriority) {
    this.prio.set(taskId, newPriority);
    this.push(newPriority * TM_SHIFT + taskId);
};

TaskManager.prototype.rmv = function(taskId) {
    this.user.delete(taskId);
    this.prio.delete(taskId);
};

TaskManager.prototype.execTop = function() {
    while (this.heap.length > 0) {
        var key = this.heap[0];
        var t = key % TM_SHIFT, p = (key - t) / TM_SHIFT;
        this.pop();
        if (this.prio.has(t) && this.prio.get(t) === p) {
            var u = this.user.get(t);
            this.rmv(t);
            return u;
        }
    }
    return -1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More hash table problems

• Implement Router Medium
• Frequency Tracker Medium
• Find Consecutive Integers from a Data Stream Medium
• Design Memory Allocator Medium
• Longest Uploaded Prefix Medium
• Design a Food Rating System Medium