3408: Design-Task-Manager
Medium

table of contents

This question took similar ideas from yesterday’s question. Simply put, it follows a similar format where whenever we edit a taskId’s priority, we can simply invalidate the original priority and append the new one onto the priority_queue.

We can do this by keeping 2 unordered_map (taskPriority and taskUser). Since we only need to check for valid tasks when we are executing the task with the highest priority (from taskPriority), we can do this by seeing if the priority value from taskPriority matches the one from the top value of priorityTasks:

unordered_map<int, int> taskPriority;           // taskId -> priority
unordered_map<int, int> taskUser;               // taskId -> userId
priority_queue<pair<int, int>> priorityTasks;   // priority_queue({priority, taskId})

To start off, whenever we add a new task, we simply:

void add(int userId, int taskId, int priority) {
    priorityTasks.emplace(priority, taskId);    // add the task to priority_queue
    taskPriority[taskId] = priority;            // add taskId -> priority mapping
    taskUser[taskId] = userId;                  // add taskId -> userId mapping
}

Then, when we initialise a new TaskManager, we can simply iterate through every element and run the add operation:

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

Now, if we want to edit a taskId’s priority, we can simply append the newPriority onto priorityTasks and update its priority:

void edit(int taskId, int newPriority) {
    priorityTasks.emplace(newPriority, taskId);
    taskPriority[taskId] = newPriority;
}

Similarly, if we want to remove a taskId, we just set its taskPriority to -1 so any attempts at validating the request fails (as it will never match any previous priority value that has been set):

void rmv(int taskId) {
    taskPriority[taskId] = -1;
}

Finally, if we want to execute the task with the highest priority, we can just iterate through and pop all the highest priority tasks until we find one that is valid:

int execTop() {
    while (!priorityTasks.empty()) {
        pair<int, int> front = priorityTasks.top(); // front.first == priority, front.second == taskId
        priorityTasks.pop();

        if (taskPriority[front.second] == front.first) {
            taskPriority[front.second] = -1;
            return taskUser[front.second];
        }
    }
    return -1;
}

code

class TaskManager {
public:
    TaskManager(vector<vector<int>>& tasks) {
        for (vector<int>& task : tasks) {
            add(task[0], task[1], task[2]);
        }
    }
    
    void add(int userId, int taskId, int priority) {
        priorityTasks.emplace(priority, taskId);
        taskPriority[taskId] = priority;
        taskUser[taskId] = userId;
    }
    
    void edit(int taskId, int newPriority) {
        priorityTasks.emplace(newPriority, taskId);
        taskPriority[taskId] = newPriority;
    }
    
    void rmv(int taskId) {
        taskPriority[taskId] = -1;
    }
    
    int execTop() {
        while (!priorityTasks.empty()) {
            pair<int, int> front = priorityTasks.top();
            priorityTasks.pop();

            if (taskPriority[front.second] == front.first) {
                taskPriority[front.second] = -1;
                return taskUser[front.second];
            }
        }
        return -1;
    }
private:
    unordered_map<int, int> taskPriority;
    unordered_map<int, int> taskUser;
    priority_queue<pair<int, int>> priorityTasks;
};

/**
 * 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();
 */

complexity

time taken