Design Task Manager

Problem

There is a task management system that allows users to manage their tasks, each associated with a priority. The system should efficiently handle adding, modifying, executing, and removing tasks.

Implement the TaskManager class:

• TaskManager(vector<vector<int>>& tasks) initializes the task manager with a list of user-task-priority triples. Each element in the input list is of the form [userId, taskId, priority], which adds a task to the specified user with the given priority.

• void add(int userId, int taskId, int priority) adds a task with the specified taskId and priority to the user with userId. It is guaranteed that taskId does not exist in the system.

• void edit(int taskId, int newPriority) updates the priority of the existing taskId to newPriority. It is guaranteed that taskId exists in the system.

• void rmv(int taskId) removes the task identified by taskId from the system. It is guaranteed that taskId exists in the system.

• int execTop() executes the task with the highest priority across all users. If there are multiple tasks with the same highest priority, execute the one with the highest taskId. After executing, the****taskId**** is removed from the system. Return the userId associated with the executed task. If no tasks are available, return -1.

Note that a user may be assigned multiple tasks.

Examples

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**
TaskManager taskManager = new TaskManager([[1, 101, 10], [2, 102, 20], [3,
103, 15]]); // Initializes with three tasks for Users 1, 2, and 3.  
taskManager.add(4, 104, 5); // Adds task 104 with priority 5 for User 4.  
taskManager.edit(102, 8); // Updates priority of task 102 to 8.  
taskManager.execTop(); // return 3. Executes task 103 for User 3.  
taskManager.rmv(101); // Removes task 101 from the system.  
taskManager.add(5, 105, 15); // Adds task 105 with priority 15 for User 5.  
taskManager.execTop(); // return 5. Executes task 105 for User 5.

Constraints

• 1 <= tasks.length <= 10^5
• 0 <= userId <= 10^5
• 0 <= taskId <= 10^5
• 0 <= priority <= 10^9
• 0 <= newPriority <= 10^9
• At most 2 * 10^5 calls will be made in total to add, edit, rmv, and execTop methods.
• The input is generated such that taskId will be valid.

Solution

Method 1 – Hash Maps and Max Heap (Priority Queue)

Intuition

We need to efficiently support adding, editing, removing, and executing the highest-priority task. By using a hash map for fast task lookup and a max heap (priority queue) for quick access to the top task, we can achieve all operations efficiently. We use lazy deletion in the heap to handle removals and edits.

Approach

1. Use a hash map taskMap to store taskId -> (userId, priority).
2. Use a max heap (priority queue) to store tuples (-priority, -taskId, taskId) for quick access to the highest-priority, highest-taskId task.
3. For add, insert into both the map and the heap.
4. For edit, update the map and push the new priority to the heap (old heap entries are ignored via lazy deletion).
5. For rmv, remove from the map (heap entries are ignored via lazy deletion).
6. For execTop, pop from the heap until a valid task is found (exists in the map and priority matches), then remove it from the map and return the userId. If no valid task, return -1.

Code

C++

class TaskManager {
    unordered_map<int, pair<int, int>> taskMap; // taskId -> (userId, priority)
    priority_queue<tuple<int, int, int>> pq; // (-priority, -taskId, taskId)
public:
    TaskManager(vector<vector<int>>& tasks) {
        for (auto& t : tasks) {
            int user = t[0], task = t[1], prio = t[2];
            taskMap[task] = {user, prio};
            pq.emplace(-prio, -task, task);
        }
    }
    void add(int userId, int taskId, int priority) {
        taskMap[taskId] = {userId, priority};
        pq.emplace(-priority, -taskId, taskId);
    }
    void edit(int taskId, int newPriority) {
        auto& [user, _] = taskMap[taskId];
        taskMap[taskId] = {user, newPriority};
        pq.emplace(-newPriority, -taskId, taskId);
    }
    void rmv(int taskId) {
        taskMap.erase(taskId);
    }
    int execTop() {
        while (!pq.empty()) {
            auto [negPrio, negTask, taskId] = pq.top();
            pq.pop();
            if (taskMap.count(taskId) && taskMap[taskId].second == -negPrio) {
                int userId = taskMap[taskId].first;
                taskMap.erase(taskId);
                return userId;
            }
        }
        return -1;
    }
};

Go

type Task struct {
    prio, taskId int
}
type TaskManager struct {
    taskMap map[int][2]int
    pq      *TaskHeap
}
type TaskHeap []Task
func (h TaskHeap) Len() int           { return len(h) }
func (h TaskHeap) Less(i, j int) bool { if h[i].prio != h[j].prio { return h[i].prio > h[j].prio } else { return h[i].taskId > h[j].taskId } }
func (h TaskHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *TaskHeap) Push(x interface{}) { *h = append(*h, x.(Task)) }
func (h *TaskHeap) Pop() interface{}   { old := *h; n := len(old); x := old[n-1]; *h = old[:n-1]; return x }
func Constructor(tasks [][]int) TaskManager {
    h := &TaskHeap{}
    tm := TaskManager{taskMap: map[int][2]int{}, pq: h}
    for _, t := range tasks {
        user, task, prio := t[0], t[1], t[2]
        tm.taskMap[task] = [2]int{user, prio}
        heap.Push(h, Task{prio, task})
    }
    return tm
}
func (tm *TaskManager) Add(userId, taskId, priority int) {
    tm.taskMap[taskId] = [2]int{userId, priority}
    heap.Push(tm.pq, Task{priority, taskId})
}
func (tm *TaskManager) Edit(taskId, newPriority int) {
    user := tm.taskMap[taskId][0]
    tm.taskMap[taskId] = [2]int{user, newPriority}
    heap.Push(tm.pq, Task{newPriority, taskId})
}
func (tm *TaskManager) Rmv(taskId int) {
    delete(tm.taskMap, taskId)
}
func (tm *TaskManager) ExecTop() int {
    for tm.pq.Len() > 0 {
        t := heap.Pop(tm.pq).(Task)
        if v, ok := tm.taskMap[t.taskId]; ok && v[1] == t.prio {
            delete(tm.taskMap, t.taskId)
            return v[0]
        }
    }
    return -1
}

Java

import java.util.*;
public class TaskManager {
    private Map<Integer, int[]> taskMap = new HashMap<>(); // taskId -> [userId, priority]
    private PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0]!=b[0]?b[0]-a[0]:b[1]-a[1]); // [priority, taskId]
    public TaskManager(List<List<Integer>> tasks) {
        for (List<Integer> t : tasks) {
            int user = t.get(0), task = t.get(1), prio = t.get(2);
            taskMap.put(task, new int[]{user, prio});
            pq.offer(new int[]{prio, task});
        }
    }
    public void add(int userId, int taskId, int priority) {
        taskMap.put(taskId, new int[]{userId, priority});
        pq.offer(new int[]{priority, taskId});
    }
    public void edit(int taskId, int newPriority) {
        int userId = taskMap.get(taskId)[0];
        taskMap.put(taskId, new int[]{userId, newPriority});
        pq.offer(new int[]{newPriority, taskId});
    }
    public void rmv(int taskId) {
        taskMap.remove(taskId);
    }
    public int execTop() {
        while (!pq.isEmpty()) {
            int[] top = pq.peek();
            int prio = top[0], taskId = top[1];
            if (taskMap.containsKey(taskId) && taskMap.get(taskId)[1] == prio) {
                int userId = taskMap.get(taskId)[0];
                taskMap.remove(taskId);
                pq.poll();
                return userId;
            }
            pq.poll();
        }
        return -1;
    }
}

Kotlin

import java.util.PriorityQueue
class TaskManager(tasks: List<List<Int>>) {
    private val taskMap = mutableMapOf<Int, Pair<Int, Int>>()
    private val pq = PriorityQueue(compareByDescending<Pair<Int, Int>> { it.first }.thenByDescending { it.second })
    init {
        for (t in tasks) {
            val (user, task, prio) = t
            taskMap[task] = user to prio
            pq.add(prio to task)
        }
    }
    fun add(userId: Int, taskId: Int, priority: Int) {
        taskMap[taskId] = userId to priority
        pq.add(priority to taskId)
    }
    fun edit(taskId: Int, newPriority: Int) {
        val user = taskMap[taskId]!!.first
        taskMap[taskId] = user to newPriority
        pq.add(newPriority to taskId)
    }
    fun rmv(taskId: Int) {
        taskMap.remove(taskId)
    }
    fun execTop(): Int {
        while (pq.isNotEmpty()) {
            val (prio, taskId) = pq.poll()
            if (taskMap[taskId]?.second == prio) {
                val user = taskMap[taskId]!!.first
                taskMap.remove(taskId)
                return user
            }
        }
        return -1
    }
}

Python

import heapq
class TaskManager:
    def __init__(self, tasks: list[list[int]]):
        self.taskMap = {}
        self.pq = []
        for user, task, prio in tasks:
            self.taskMap[task] = (user, prio)
            heapq.heappush(self.pq, (-prio, -task, task))
    def add(self, userId: int, taskId: int, priority: int) -> None:
        self.taskMap[taskId] = (userId, priority)
        heapq.heappush(self.pq, (-priority, -taskId, taskId))
    def edit(self, taskId: int, newPriority: int) -> None:
        user, _ = self.taskMap[taskId]
        self.taskMap[taskId] = (user, newPriority)
        heapq.heappush(self.pq, (-newPriority, -taskId, taskId))
    def rmv(self, taskId: int) -> None:
        self.taskMap.pop(taskId, None)
    def execTop(self) -> int:
        while self.pq:
            negPrio, negTask, taskId = heapq.heappop(self.pq)
            if taskId in self.taskMap and self.taskMap[taskId][1] == -negPrio:
                userId = self.taskMap[taskId][0]
                del self.taskMap[taskId]
                return userId
        return -1

Rust

use std::collections::{BinaryHeap, HashMap};
struct TaskManager {
    task_map: HashMap<i32, (i32, i32)>,
    pq: BinaryHeap<(i32, i32, i32)>, // (priority, taskId, userId)
}
impl TaskManager {
    fn new(tasks: Vec<Vec<i32>>) -> Self {
        let mut task_map = HashMap::new();
        let mut pq = BinaryHeap::new();
        for t in tasks {
            let user = t[0];
            let task = t[1];
            let prio = t[2];
            task_map.insert(task, (user, prio));
            pq.push((prio, task, user));
        }
        Self { task_map, pq }
    }
    fn add(&mut self, user_id: i32, task_id: i32, priority: i32) {
        self.task_map.insert(task_id, (user_id, priority));
        self.pq.push((priority, task_id, user_id));
    }
    fn edit(&mut self, task_id: i32, new_priority: i32) {
        let user = self.task_map[&task_id].0;
        self.task_map.insert(task_id, (user, new_priority));
        self.pq.push((new_priority, task_id, user));
    }
    fn rmv(&mut self, task_id: i32) {
        self.task_map.remove(&task_id);
    }
    fn exec_top(&mut self) -> i32 {
        while let Some((prio, task_id, user_id)) = self.pq.pop() {
            if let Some(&(u, p)) = self.task_map.get(&task_id) {
                if p == prio {
                    self.task_map.remove(&task_id);
                    return u;
                }
            }
        }
        -1
    }
}

TypeScript

class TaskManager {
    private taskMap = new Map<number, [number, number]>();
    private pq: [number, number, number][] = [];
    constructor(tasks: number[][]) {
        for (const [user, task, prio] of tasks) {
            this.taskMap.set(task, [user, prio]);
            this.pq.push([-prio, -task, task]);
        }
        this.pq.sort();
    }
    add(userId: number, taskId: number, priority: number): void {
        this.taskMap.set(taskId, [userId, priority]);
        this.pq.push([-priority, -taskId, taskId]);
        this.pq.sort();
    }
    edit(taskId: number, newPriority: number): void {
        const [user, _] = this.taskMap.get(taskId)!;
        this.taskMap.set(taskId, [user, newPriority]);
        this.pq.push([-newPriority, -taskId, taskId]);
        this.pq.sort();
    }
    rmv(taskId: number): void {
        this.taskMap.delete(taskId);
    }
    execTop(): number {
        while (this.pq.length) {
            const [negPrio, negTask, taskId] = this.pq.shift()!;
            if (this.taskMap.has(taskId) && this.taskMap.get(taskId)![1] === -negPrio) {
                const userId = this.taskMap.get(taskId)![0];
                this.taskMap.delete(taskId);
                return userId;
            }
        }
        return -1;
    }
}

Complexity

• ⏰ Time complexity: O(log n) per operation due to heap operations and hash map lookups.
• 🧺 Space complexity: O(n), where n is the number of tasks in the system.