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 makes you think of using a heap, but you need to implement the heap yourself. Although C++'s priority_queue is also a heap, it doesn’t provide a way to modify elements, which greatly limits its use.
However, the following pure-heap solution passed 660/663 test cases, and 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]; // A smaller priority means 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 task
        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 said earlier that priority_queue cannot delete elements. With lazy deletion, as long as the element that should be deleted is not the maximum, we don’t delete it.
After this problem, I finally understand why priority_queue doesn’t provide methods to modify or delete non-top elements.
Lazy deletion gets a thumbs up 👍

Note that in this problem, there are two kinds of “lazy deletion”: 1. Caused by modification: the taskId may appear repeatedly in the heap, so in the end it’s not enough to just check whether the taskId exists in the map; 2. Caused by deletion: the 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 the priority is the same
                                top_userId = map[top_taskId].second;
                                map.erase(top_taskId);
                                heap.pop();
                                return top_userId;
                        } else { // The 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();
 */

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

Syntax

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

args… are passed directly to T’s constructor
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;

    // Using push
    pair<int,int> p(1, 100);
    heap.push(p);   // will copy p into 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();
    }
}