LeetCode Daily Problem P3408: Design Task Manager

---

Timeline

Timeline

2025-09-18

init

Max heap lazy deletion

---

Problem:

P3408 Design Task Manager

https://leetcode.cn/problems/design-task-manager/description/?envType=daily-question&envId=2025-09-18

Custom max heap, TLE

This problem naturally suggests using a heap, but you need to implement a custom heap. Although C++'s priority_queue is also a heap, it does not provide methods to modify elements, which greatly limits its use.
However, the following pure heap implementation passes 660/663 test cases, but test case 660 timed out (TLE).

#include <vector>

using std::vector;

template <typename T, typename Compare = std::less<T> > class Heap {
    public:
        Heap()
        {
        }
        void push(T val)
        {
                vec.push_back(val);
                shiftUp(vec.size() - 1);
        }
        void pop()
        {
                if (vec.empty()) {
                        return;
                }
                swap(vec[0], vec.back());
                vec.pop_back();
                shiftDown(0);
        }
        T top()
        {
                return vec.front();
        }
        bool empty()
        {
                return vec.empty();
        }

        void shiftUp(size_t index)
        {
                while (index != 0) {
                        if (!cmp(vec[parent(index)], vec[index])) {
                                break;
                        }
                        // vec[index] returns a reference to the element, not a copy.
                        swap(vec[parent(index)], vec[index]);
                        index = parent(index);
                }
        }
        void shiftDown(size_t index)
        {
                int n = vec.size();
                while (true) {
                        size_t left = left_child(index);
                        size_t right = right_child(index);
                        size_t largest = index;

                        if (left < n && cmp(vec[largest], vec[left]))
                                largest = left;
                        if (right < n && cmp(vec[largest], vec[right]))
                                largest = right;
                        if (largest == index)
                                break;
                        swap(vec[index], vec[largest]);
                        index = largest;
                }
        }

        inline size_t left_child(size_t index)
        {
                return 2 * index + 1;
        }
        inline size_t right_child(size_t index)
        {
                return 2 * index + 2;
        }
        inline size_t parent(size_t index)
        {
                return (index - 1) / 2;
        }

        vector<T> vec;
        Compare cmp;
};

class TaskManager {
    public:
        TaskManager(vector<vector<int> > &tasks)
        {
                for (vector<int> task : tasks) {
                        max_heap.push(task);
                }
        }

        void add(int userId, int taskId, int priority)
        {
                vector<int> vec;
                vec.push_back(userId);
                vec.push_back(taskId);
                vec.push_back(priority);
                // Copy
                max_heap.push(vec);
        }

        void edit(int taskId, int newPriority)
        {
                int index = -1;
                int oldPriority;
                for (int i = 0; i < max_heap.vec.size(); i++) {
                        if (max_heap.vec[i][1] == taskId) {
                                index = i;
                                oldPriority = max_heap.vec[i][2];
                                max_heap.vec[i][2] = newPriority;
                                break;
                        }
                }
                if (index == -1) {
                        return;
                }

                if (oldPriority < newPriority) {
                        max_heap.shiftUp(index);
                } else {
                        max_heap.shiftDown(index);
                }
        }

        void rmv(int taskId)
        {
                int index = -1;
                int oldPriority;
                for (int i = 0; i < max_heap.vec.size(); i++) {
                        if (max_heap.vec[i][1] == taskId) {
                                index = i;
                                oldPriority = max_heap.vec[i][2];
                                break;
                        }
                }
                if (index == -1) {
                        return;
                }

                if (index == max_heap.vec.size() - 1) {
                        max_heap.vec.pop_back();
                        return;
                }

                swap(max_heap.vec.back(), max_heap.vec[index]);
                max_heap.vec.pop_back();

                if (oldPriority > max_heap.vec[index][2]) {
                        max_heap.shiftDown(index);
                } else {
                        max_heap.shiftUp(index);
                }
        }

        int execTop()
        {
                int userId;
                if (max_heap.vec.empty()) {
                        return -1;
                }
                userId = max_heap.top()[0];
                max_heap.pop();
                return userId;
        }

    private:
        struct Compare {
                bool operator()(const vector<int> &a, const vector<int> &b) const
                {
                        if (a[2] != b[2])
                                return a[2] < b[2]; // Lower priority means lower priority (i.e., smaller priority value has lower priority)
                        else
                                return a[1] < b[1];
                }
        };
        Heap<vector<int>, Compare> max_heap;
};

/**
 * 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();
 */
#include <iostream>
int main()
{
        // Step 1: Initialize tasks
        vector<vector<int> > tasks = { { 10, 26, 25 } }; // User 10, Task 26, Priority 25
        TaskManager taskManager(tasks);

        // Step 2: Delete Task 26
        taskManager.rmv(26);

        int topUser = taskManager.execTop();
        std::cout << "execTop() -> " << topUser << std::endl;

        return 0;
}

Max Heap + Lazy Deletion

We previously said that priority_queue cannot delete. Using the lazy deletion method, as long as the element that should be deleted is not the maximum, it is not deleted.
After this problem, I understand why priority_queue does not provide methods to modify or delete non-top elements.
Lazy deletion thumbs up 👍

Note that there are two types of lazy deletion in this problem: 1. Caused by modification, taskId may appear repeatedly in the heap, so it is not enough to only check whether taskId exists in the map; 2. Caused by deletion, taskId disappears;

#include <queue>
#include <unordered_map>
#include <utility>
#include <vector>

using std::pair;
using std::priority_queue;
using std::unordered_map;
using std::vector;

class TaskManager {
    private:
        unordered_map<int, pair<int, int> > map;
        priority_queue<pair<int, int> > heap;

    public:
        TaskManager(vector<vector<int> > &tasks)
        {
                int userId, taskId, priority;
                for (vector<int> &task : tasks) {
                        userId = task[0];
                        taskId = task[1];
                        priority = task[2];
                        map[taskId] = { priority, userId };
                        heap.emplace(priority, taskId);
                }
        }

        void add(int userId, int taskId, int priority)
        {
                heap.emplace(priority, taskId);
                map[taskId] = { priority, userId };
        }

        void edit(int taskId, int newPriority)
        {
                if (map.find(taskId) != map.end()) {
                        map[taskId].first = newPriority;
                        heap.emplace(newPriority, taskId);
                }
        }

        void rmv(int taskId)
        {
                map.erase(taskId);
        }

        int execTop()
        {
                int top_userId, top_taskId, top_priority;

                while (!heap.empty()) {
                        top_priority = heap.top().first;
                        top_taskId = heap.top().second;

                        if (map.find(top_taskId) != map.end() &&
                            map[top_taskId].first == top_priority) { // Exists, and priority is the same
                                top_userId = map[top_taskId].second;
                                map.erase(top_taskId);
                                heap.pop();
                                return top_userId;
                        } else { // Element that should be deleted
                                heap.pop();
                        }
                }
                return -1;
        }
};

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

Among them, heap.emplace(…) is a member function of the C++ standard library priority_queue, used to directly construct elements in place in the heap, rather than creating an object first and then copying or moving it in. It is similar to push() in functionality, but is usually more efficient than push(), especially when constructing complex objects.

Syntax

priority_queue<T> heap;
heap.emplace(args...);

args… are directly passed to the constructor of T
Equivalent to:

heap.push(T(args...));

But emplace avoids the creation of temporary objects.
Example

#include <queue>
#include <vector>
#include <iostream>
using namespace std;

int main() {
    priority_queue<pair<int,int>> heap;

    // use push
    pair<int,int> p(1, 100);
    heap.push(p);   // will copy p to the heap

    // use emplace
    heap.emplace(2, 200); // directly construct pair<int,int>(2,200) in the heap

    while (!heap.empty()) {
        cout << heap.top().first << " " << heap.top().second << endl;
        heap.pop();
    }
}