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();
    }
}