leetcode每日一题 P3408 设计任务管理器

---

时间轴

时间轴

2025-09-18

init

最大堆 懒删除

---

题目：

P3408 设计任务管理器

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

自定义最大堆，TLE

这题很自然想到用堆实现，但是要自定义实现堆，C++的 priority_queue 虽然也是堆，但是不提供修改元素的方法，使用受较大限制但是下面的写法纯用堆 660/663 个通过，660 的测试用例 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]返回的是元素的引用而不是拷贝
                        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);
                // 拷贝
                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]; // 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: 初始化任务
        vector<vector<int> > tasks = { { 10, 26, 25 } }; // 用户 10，任务 26，优先级 25
        TaskManager taskManager(tasks);

        // Step 2: 删除任务 26
        taskManager.rmv(26);

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

        return 0;
}

最大堆 + 懒删除

我们之前说 priority_queue 不能删除。使用懒删除的方法，只要这个应该删除的元素不是最大值就不删除它。经过此题我算是明白为什么 priority_queue 不提供修改或删除非堆顶元素的方法了。懒删除点赞 👍

注意该题懒删除"懒删"的有两种： 1.修改产生的，taskId 可能在堆里重复出现，因此最后只通过 taskId 是否在 map 中存在是不行的； 2.删除产生的，taskId 消失；

#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) { // 存在,且priority相同
                                top_userId = map[top_taskId].second;
                                map.erase(top_taskId);
                                heap.pop();
                                return top_userId;
                        } else { // 应该删除的元素
                                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();
 */

其中 heap.emplace(…) 是 C++ 标准库 priority_queue 的一个成员函数，用来 在堆中直接原地构造元素，而不是先创建对象再拷贝或移动进去。它和 push() 功能类似，但通常比 push() 更高效，尤其是构造复杂对象时。

语法

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

args… 会被直接传给 T 的构造函数等价于：

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

但 emplace 避免了 临时对象的创建。举例

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

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

    // 使用 push
    pair<int,int> p(1, 100);
    heap.push(p);   // 会拷贝 p 到堆里

    // 使用 emplace
    heap.emplace(2, 200); // 直接在堆中构造 pair<int,int>(2,200)

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