3408. Design Task Manager

• Time:
  • Constructor: $O(n\logn)$
  • add(userId: int, taskId: int, priority: int): $O(\log n)$
  • edit(taskId: int, newPriority: int): $O(\log n)$
  • rmv(taskId: int): $O(\log n)$
  • execTop(): $O(\log n)$
• Space: $O(|\texttt{tasks}|)$

C++JavaPython

struct Task {
  int userId;
  int taskId;
  int priority;

  Task() = default;
  Task(int u, int t, int p) : userId(u), taskId(t), priority(p) {}

  bool operator<(const Task& other) const {
    return priority == other.priority ? taskId > other.taskId
                                      : priority > other.priority;
  }
};

class TaskManager {
 public:
  unordered_map<int, Task> taskMap;  // {taskId: Task}
  set<Task> taskSet;  // Stores tasks sorted by priority and taskId.

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

  void add(int userId, int taskId, int priority) {
    const Task task(userId, taskId, priority);
    taskMap[taskId] = task;
    taskSet.insert(task);
  }

  void edit(int taskId, int newPriority) {
    const Task task = taskMap[taskId];
    taskSet.erase(task);
    const Task editedTask = Task(task.userId, task.taskId, newPriority);
    taskSet.insert(editedTask);
    taskMap[taskId] = editedTask;
  }

  void rmv(int taskId) {
    const Task task = taskMap[taskId];
    taskSet.erase(task);
    taskMap.erase(taskId);
  }

  int execTop() {
    if (taskSet.empty())
      return -1;
    const Task task = *taskSet.begin();
    taskSet.erase(task);
    taskMap.erase(task.taskId);
    return task.userId;
  }
};

class Task implements Comparable<Task> {
  public int userId;
  public int taskId;
  public int priority;

  public Task() {}

  public Task(int userId, int taskId, int priority) {
    this.userId = userId;
    this.taskId = taskId;
    this.priority = priority;
  }

  @Override
  public int compareTo(Task other) {
    return this.priority == other.priority ? Integer.compare(other.taskId, this.taskId)
                                           : Integer.compare(other.priority, this.priority);
  }
}

class TaskManager {

  public TaskManager(List<List<Integer>> tasks) {
    taskMap = new HashMap<>();
    taskSet = new TreeSet<>();
    for (List<Integer> task : tasks)
      add(task.get(0), task.get(1), task.get(2));
  }

  public void add(int userId, int taskId, int priority) {
    Task task = new Task(userId, taskId, priority);
    taskMap.put(taskId, task);
    taskSet.add(task);
  }

  public void edit(int taskId, int newPriority) {
    Task task = taskMap.get(taskId);
    taskSet.remove(task);
    Task editedTask = new Task(task.userId, taskId, newPriority);
    taskSet.add(editedTask);
    taskMap.put(taskId, editedTask);
  }

  public void rmv(int taskId) {
    Task task = taskMap.get(taskId);
    taskSet.remove(task);
    taskMap.remove(taskId);
  }

  public int execTop() {
    if (taskSet.isEmpty())
      return -1;
    Task task = taskSet.iterator().next();
    taskSet.remove(task);
    taskMap.remove(task.taskId);
    return task.userId;
  }

  private Map<Integer, Task> taskMap = new HashMap<>(); // {taskId: Task}
  private Set<Task> taskSet; // Stores tasks sorted by priority and taskId.
}

from dataclasses import dataclass
from sortedcontainers import SortedDict, SortedSet


@dataclass(frozen=True)
class Task:
  userId: int
  taskId: int
  priority: int

  def __lt__(self, other):
    if self.priority == other.priority:
      return self.taskId > other.taskId
    return self.priority > other.priority


class TaskManager:
  def __init__(self, tasks: list[list[int]]):
    self.taskMap = SortedDict()  # {taskId: Task}, keeps tasks sorted by taskId
    self.taskSet = SortedSet()  # Stores tasks sorted by priority and taskId
    for task in tasks:
      self.add(task[0], task[1], task[2])

  def add(self, userId: int, taskId: int, priority: int) -> None:
    task = Task(userId, taskId, priority)
    self.taskMap[taskId] = task
    self.taskSet.add(task)

  def edit(self, taskId: int, newPriority: int) -> None:
    task = self.taskMap[taskId]
    self.taskSet.remove(task)
    editedTask = Task(task.userId, taskId, newPriority)
    self.taskSet.add(editedTask)
    self.taskMap[taskId] = editedTask

  def rmv(self, taskId: int) -> None:
    task = self.taskMap[taskId]
    self.taskSet.remove(task)
    del self.taskMap[taskId]

  def execTop(self):
    if not self.taskSet:
      return -1
    task = self.taskSet.pop(0)
    del self.taskMap[task.taskId]
    return task.userId