3408. Design Task Manager

Description

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.

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⁵
0 <= userId <= 10⁵
0 <= taskId <= 10⁵
0 <= priority <= 10⁹
0 <= newPriority <= 10⁹
At most 2 * 10⁵ calls will be made in total to add, edit, rmv, and execTop methods.
The input is generated such that taskId will be valid.

Solutions

Solution 1: Hash Map + Ordered Set

Thinking

Up to \(2\times 10^5\) operations require fetching the highest-priority (then highest-id) task and editing or deleting by \(\textit{taskId}\). Scanning every task on \(\textit{execTop}\) is too slow.

A hash map finds a task's user and priority in \(O(1)\) but not the global maximum. A heap or ordered set keeps the maximum, but edits must locate the old tuple.

We store \(\textit{taskId}\mapsto(\textit{userId},\textit{priority})\) in a hash map \(\textit{d}\), and \((-\textit{priority},-\textit{taskId})\) in an ordered set so the best task sits at the front. Each update touches both structures; \(\textit{execTop}\) pops the first set element.

We use a hash map \(\text{d}\) to store task information, where the key is the task ID and the value is a tuple \((\text{userId}, \text{priority})\) representing the user ID and the priority of the task.

We use an ordered set \(\text{st}\) to store all tasks currently in the system, where each element is a tuple \((-\text{priority}, -\text{taskId})\) representing the negative priority and negative task ID. We use negative values so that the task with the highest priority and largest task ID appears first in the ordered set.

For each operation, we can process as follows:

Initialization: For each task \((\text{userId}, \text{taskId}, \text{priority})\), add it to the hash map \(\text{d}\) and the ordered set \(\text{st}\).
Add Task: Add the task \((\text{userId}, \text{taskId}, \text{priority})\) to the hash map \(\text{d}\) and the ordered set \(\text{st}\).
Edit Task: Retrieve the user ID and old priority for the given task ID from the hash map \(\text{d}\), remove the old task information from the ordered set \(\text{st}\), then add the new task information to both the hash map and the ordered set.
Remove Task: Retrieve the priority for the given task ID from the hash map \(\text{d}\), remove the task information from the ordered set \(\text{st}\), and delete the task from the hash map.
Execute Top Priority Task: If the ordered set \(\text{st}\) is empty, return -1. Otherwise, take the first element from the ordered set, get the task ID, retrieve the corresponding user ID from the hash map, and remove the task from both the hash map and the ordered set. Finally, return the user ID.

For time complexity, initialization requires \(O(n \log n)\) time, where \(n\) is the number of initial tasks. Each add, edit, remove, and execute operation requires \(O(\log m)\) time, where \(m\) is the current number of tasks in the system. Since the total number of operations does not exceed \(2 \times 10^5\), the overall time complexity is acceptable. The space complexity is \(O(n + m)\) for storing the hash map and ordered set.

Python3JavaC++GoTypeScript

class TaskManager:

    def __init__(self, tasks: List[List[int]]):
        self.d = {}
        self.st = SortedList()
        for task in tasks:
            self.add(*task)

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

    def edit(self, taskId: int, newPriority: int) -> None:
        userId, priority = self.d[taskId]
        self.st.discard((-priority, -taskId))
        self.d[taskId] = (userId, newPriority)
        self.st.add((-newPriority, -taskId))

    def rmv(self, taskId: int) -> None:
        _, priority = self.d[taskId]
        self.d.pop(taskId)
        self.st.remove((-priority, -taskId))

    def execTop(self) -> int:
        if not self.st:
            return -1
        taskId = -self.st.pop(0)[1]
        userId, _ = self.d[taskId]
        self.d.pop(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()

class TaskManager {
    private final Map<Integer, int[]> d = new HashMap<>();
    private final TreeSet<int[]> st = new TreeSet<>((a, b) -> {
        if (a[0] == b[0]) {
            return b[1] - a[1];
        }
        return b[0] - a[0];
    });

    public TaskManager(List<List<Integer>> tasks) {
        for (var task : tasks) {
            add(task.get(0), task.get(1), task.get(2));
        }
    }

    public void add(int userId, int taskId, int priority) {
        d.put(taskId, new int[] {userId, priority});
        st.add(new int[] {priority, taskId});
    }

    public void edit(int taskId, int newPriority) {
        var e = d.get(taskId);
        int userId = e[0], priority = e[1];
        st.remove(new int[] {priority, taskId});
        st.add(new int[] {newPriority, taskId});
        d.put(taskId, new int[] {userId, newPriority});
    }

    public void rmv(int taskId) {
        var e = d.remove(taskId);
        int priority = e[1];
        st.remove(new int[] {priority, taskId});
    }

    public int execTop() {
        if (st.isEmpty()) {
            return -1;
        }
        var e = st.pollFirst();
        var t = d.remove(e[1]);
        return t[0];
    }
}

/**
 * Your TaskManager object will be instantiated and called as such:
 * TaskManager obj = new TaskManager(tasks);
 * obj.add(userId,taskId,priority);
 * obj.edit(taskId,newPriority);
 * obj.rmv(taskId);
 * int param_4 = obj.execTop();
 */

class TaskManager {
private:
    unordered_map<int, pair<int, int>> d;
    set<pair<int, int>> st;

public:
    TaskManager(vector<vector<int>>& tasks) {
        for (const auto& task : tasks) {
            add(task[0], task[1], task[2]);
        }
    }

    void add(int userId, int taskId, int priority) {
        d[taskId] = {userId, priority};
        st.insert({-priority, -taskId});
    }

    void edit(int taskId, int newPriority) {
        auto [userId, priority] = d[taskId];
        st.erase({-priority, -taskId});
        st.insert({-newPriority, -taskId});
        d[taskId] = {userId, newPriority};
    }

    void rmv(int taskId) {
        auto [userId, priority] = d[taskId];
        st.erase({-priority, -taskId});
        d.erase(taskId);
    }

    int execTop() {
        if (st.empty()) {
            return -1;
        }
        auto e = *st.begin();
        st.erase(st.begin());
        int taskId = -e.second;
        int userId = d[taskId].first;
        d.erase(taskId);
        return userId;
    }
};

/**
 * Your TaskManager object will be instantiated and called as such:
 * TaskManager* obj = new TaskManager(tasks);
 * obj->add(userId,taskId,priority);
 * obj->edit(taskId,newPriority);
 * obj->rmv(taskId);
 * int param_4 = obj->execTop();
 */

type TaskManager struct {
    d  map[int][2]int
    st *redblacktree.Tree[int, int]
}

func encode(priority, taskId int) int {
    return (priority << 32) | taskId
}

func comparator(a, b int) int {
    if a > b {
        return -1
    } else if a < b {
        return 1
    }
    return 0
}

func Constructor(tasks [][]int) TaskManager {
    tm := TaskManager{
        d:  make(map[int][2]int),
        st: redblacktree.NewWith[int, int](comparator),
    }
    for _, task := range tasks {
        tm.Add(task[0], task[1], task[2])
    }
    return tm
}

func (this *TaskManager) Add(userId int, taskId int, priority int) {
    this.d[taskId] = [2]int{userId, priority}
    this.st.Put(encode(priority, taskId), taskId)
}

func (this *TaskManager) Edit(taskId int, newPriority int) {
    if e, ok := this.d[taskId]; ok {
        priority := e[1]
        this.st.Remove(encode(priority, taskId))
        this.d[taskId] = [2]int{e[0], newPriority}
        this.st.Put(encode(newPriority, taskId), taskId)
    }
}

func (this *TaskManager) Rmv(taskId int) {
    if e, ok := this.d[taskId]; ok {
        priority := e[1]
        delete(this.d, taskId)
        this.st.Remove(encode(priority, taskId))
    }
}

func (this *TaskManager) ExecTop() int {
    if this.st.Empty() {
        return -1
    }
    it := this.st.Iterator()
    it.Next()
    taskId := it.Value()
    if e, ok := this.d[taskId]; ok {
        delete(this.d, taskId)
        this.st.Remove(it.Key())
        return e[0]
    }
    return -1
}

/**
 * Your TaskManager object will be instantiated and called as such:
 * obj := Constructor(tasks);
 * obj.Add(userId,taskId,priority);
 * obj.Edit(taskId,newPriority);
 * obj.Rmv(taskId);
 * param_4 := obj.ExecTop();
 */

class TaskManager {
    private d: Map<number, [number, number]>;
    private pq: PriorityQueue<[number, number]>;

    constructor(tasks: number[][]) {
        this.d = new Map();
        this.pq = new PriorityQueue<[number, number]>((a, b) => {
            if (a[0] === b[0]) {
                return b[1] - a[1];
            }
            return b[0] - a[0];
        });
        for (const task of tasks) {
            this.add(task[0], task[1], task[2]);
        }
    }

    add(userId: number, taskId: number, priority: number): void {
        this.d.set(taskId, [userId, priority]);
        this.pq.enqueue([priority, taskId]);
    }

    edit(taskId: number, newPriority: number): void {
        const e = this.d.get(taskId);
        if (!e) return;
        const userId = e[0];
        this.d.set(taskId, [userId, newPriority]);
        this.pq.enqueue([newPriority, taskId]);
    }

    rmv(taskId: number): void {
        this.d.delete(taskId);
    }

    execTop(): number {
        while (!this.pq.isEmpty()) {
            const [priority, taskId] = this.pq.dequeue();
            const e = this.d.get(taskId);
            if (e && e[1] === priority) {
                this.d.delete(taskId);
                return e[0];
            }
        }
        return -1;
    }
}

/**
 * Your TaskManager object will be instantiated and called as such:
 * var obj = new TaskManager(tasks)
 * obj.add(userId,taskId,priority)
 * obj.edit(taskId,newPriority)
 * obj.rmv(taskId)
 * var param_4 = obj.execTop()
 */

3408. Design Task Manager

Description

Solutions

Solution 1: Hash Map + Ordered Set

Comments