Question

2590. 设计一个待办事项清单

English Version

题目描述

设计一个待办事项清单，用户可以添加 任务 ，标记任务为 完成状态 ，或获取待办任务列表。用户还可以为任务添加 标签 ，并可以按照特定标签筛选任务。

实现 TodoList 类：

• TodoList() 初始化对象。
• int addTask(int userId, String taskDescription, int dueDate, List<String> tags) 为用户 ID 为 userId 的用户添加一个任务，该任务的到期日期为 dueDate ，附带了一个标签列表 tags 。返回值为任务的 ID 。该 ID 从 1 开始，依次 递增。即，第一个任务的ID应为 1 ，第二个任务的 ID 应为 2 ，以此类推。
• List<String> getAllTasks(int userId) 返回未标记为完成状态的 ID 为 userId 的用户的所有任务列表，按照到期日期排序。如果用户没有未完成的任务，则应返回一个空列表。
• List<String> getTasksForTag(int userId, String tag) 返回 ID 为 userId 的用户未标记为完成状态且具有 tag 标签之一的所有任务列表，按照到期日期排序。如果不存在此类任务，则返回一个空列表。
• void completeTask(int userId, int taskId) 仅在任务存在且 ID 为 userId 的用户拥有此任务且它是未完成状态时，将 ID 为 taskId 的任务标记为已完成状态。

 

示例 1 ：

输入
["TodoList", "addTask", "addTask", "getAllTasks", "getAllTasks", "addTask", "getTasksForTag", "completeTask", "completeTask", "getTasksForTag", "getAllTasks"]
[[], [1, "Task1", 50, []], [1, "Task2", 100, ["P1"]], [1], [5], [1, "Task3", 30, ["P1"]], [1, "P1"], [5, 1], [1, 2], [1, "P1"], [1]]
输出
[null, 1, 2, ["Task1", "Task2"], [], 3, ["Task3", "Task2"], null, null, ["Task3"], ["Task3", "Task1"]]

解释
TodoList todoList = new TodoList(); 
todoList.addTask(1, "Task1", 50, []); // 返回1。为ID为1的用户添加一个新任务。 
todoList.addTask(1, "Task2", 100, ["P1"]); // 返回2。为ID为1的用户添加另一个任务，并给它添加标签“P1”。 
todoList.getAllTasks(1); // 返回["Task1", "Task2"]。用户1目前有两个未完成的任务。 
todoList.getAllTasks(5); // 返回[]。用户5目前没有任务。 
todoList.addTask(1, "Task3", 30, ["P1"]); // 返回3。为ID为1的用户添加另一个任务，并给它添加标签“P1”。 
todoList.getTasksForTag(1, "P1"); // 返回["Task3", "Task2"]。返回ID为1的用户未完成的带有“P1”标签的任务。 
todoList.completeTask(5, 1); // 不做任何操作，因为任务1不属于用户5。 
todoList.completeTask(1, 2); // 将任务2标记为已完成。 
todoList.getTasksForTag(1, "P1"); // 返回["Task3"]。返回ID为1的用户未完成的带有“P1”标签的任务。 
                  // 注意，现在不包括 “Task2” ，因为它已经被标记为已完成。 
todoList.getAllTasks(1); // 返回["Task3", "Task1"]。用户1现在有两个未完成的任务。

 

提示：

• 1 <= userId, taskId, dueDate <= 100
• 0 <= tags.length <= 100
• 1 <= taskDescription.length <= 50
• 1 <= tags[i].length, tag.length <= 20
• 所有的 dueDate 值都是唯一的。
• 所有字符串都由小写和大写英文字母和数字组成。
• 每个方法最多被调用 100 次。

解法

方法一：哈希表 + 有序集合

我们使用哈希表 $tasks$ 记录每个用户的任务集合，其中键为用户 ID，值为一个有序集合，按照任务的截止日期排序。另外用一个变量 $i$ 记录当前任务的 ID。

调用 addTask 方法时，我们将任务添加到对应用户的任务集合中，返回任务 ID。此操作的时间复杂度为 $O(\log n)$。

调用 getAllTasks 方法时，我们遍历对应用户的任务集合，将未完成的任务的描述添加到结果列表中，返回结果列表。此操作的时间复杂度为 $O(n)$。

调用 getTasksForTag 方法时，我们遍历对应用户的任务集合，将未完成的任务的描述添加到结果列表中，返回结果列表。此操作的时间复杂度为 $O(n)$。

调用 completeTask 方法时，我们遍历对应用户的任务集合，将任务 ID 为 $taskId$ 的任务标记为已完成。此操作的时间复杂度为 $(n)$。

空间复杂度 $O(n)$。其中 $n$ 为所有任务的数量。

from sortedcontainers import SortedList


class TodoList:
  def __init__(self):
    self.i = 1
    self.tasks = defaultdict(SortedList)

  def addTask(
    self, userId: int, taskDescription: str, dueDate: int, tags: List[str]
  ) -> int:
    taskId = self.i
    self.i += 1
    self.tasks[userId].add([dueDate, taskDescription, set(tags), taskId, False])
    return taskId

  def getAllTasks(self, userId: int) -> List[str]:
    return [x[1] for x in self.tasks[userId] if not x[4]]

  def getTasksForTag(self, userId: int, tag: str) -> List[str]:
    return [x[1] for x in self.tasks[userId] if not x[4] and tag in x[2]]

  def completeTask(self, userId: int, taskId: int) -> None:
    for task in self.tasks[userId]:
      if task[3] == taskId:
        task[4] = True
        break


# Your TodoList object will be instantiated and called as such:
# obj = TodoList()
# param_1 = obj.addTask(userId,taskDescription,dueDate,tags)
# param_2 = obj.getAllTasks(userId)
# param_3 = obj.getTasksForTag(userId,tag)
# obj.completeTask(userId,taskId)

class Task {
  int taskId;
  String taskName;
  int dueDate;
  Set<String> tags;
  boolean finish;

  public Task(int taskId, String taskName, int dueDate, Set<String> tags) {
    this.taskId = taskId;
    this.taskName = taskName;
    this.dueDate = dueDate;
    this.tags = tags;
  }
}

class TodoList {
  private int i = 1;
  private Map<Integer, TreeSet<Task>> tasks = new HashMap<>();

  public TodoList() {
  }

  public int addTask(int userId, String taskDescription, int dueDate, List<String> tags) {
    Task task = new Task(i++, taskDescription, dueDate, new HashSet<>(tags));
    tasks.computeIfAbsent(userId, k -> new TreeSet<>(Comparator.comparingInt(a -> a.dueDate)))
      .add(task);
    return task.taskId;
  }

  public List<String> getAllTasks(int userId) {
    List<String> ans = new ArrayList<>();
    if (tasks.containsKey(userId)) {
      for (Task task : tasks.get(userId)) {
        if (!task.finish) {
          ans.add(task.taskName);
        }
      }
    }
    return ans;
  }

  public List<String> getTasksForTag(int userId, String tag) {
    List<String> ans = new ArrayList<>();
    if (tasks.containsKey(userId)) {
      for (Task task : tasks.get(userId)) {
        if (task.tags.contains(tag) && !task.finish) {
          ans.add(task.taskName);
        }
      }
    }
    return ans;
  }

  public void completeTask(int userId, int taskId) {
    if (tasks.containsKey(userId)) {
      for (Task task : tasks.get(userId)) {
        if (task.taskId == taskId) {
          task.finish = true;
          break;
        }
      }
    }
  }
}

/**
 * Your TodoList object will be instantiated and called as such:
 * TodoList obj = new TodoList();
 * int param_1 = obj.addTask(userId,taskDescription,dueDate,tags);
 * List<String> param_2 = obj.getAllTasks(userId);
 * List<String> param_3 = obj.getTasksForTag(userId,tag);
 * obj.completeTask(userId,taskId);
 */

use std::collections::{ HashMap, HashSet };

#[derive(Clone)]
struct Task {
  task_id: i32,
  description: String,
  tags: HashSet<String>,
  due_date: i32,
}

struct TodoList {
  /// The global task id
  id: i32,
  /// The mapping from `user_id` to `task`
  user_map: HashMap<i32, Vec<Task>>,
}

impl TodoList {
  fn new() -> Self {
    Self {
      id: 1,
      user_map: HashMap::new(),
    }
  }

  fn add_task(
    &mut self,
    user_id: i32,
    task_description: String,
    due_date: i32,
    tags: Vec<String>
  ) -> i32 {
    if self.user_map.contains_key(&user_id) {
      // Just add the task
      self.user_map
        .get_mut(&user_id)
        .unwrap()
        .push(Task {
          task_id: self.id,
          description: task_description,
          tags: tags.into_iter().collect::<HashSet<String>>(),
          due_date,
        });
      // Increase the global id
      self.id += 1;
      return self.id - 1;
    }
    // Otherwise, create a new user
    self.user_map.insert(
      user_id,
      vec![Task {
        task_id: self.id,
        description: task_description,
        tags: tags.into_iter().collect::<HashSet<String>>(),
        due_date,
      }]
    );
    self.id += 1;
    self.id - 1
  }

  fn get_all_tasks(&self, user_id: i32) -> Vec<String> {
    if
      !self.user_map.contains_key(&user_id) ||
      self.user_map.get(&user_id).unwrap().is_empty()
    {
      return vec![];
    }
    // Get the task vector
    let mut ret_vec = (*self.user_map.get(&user_id).unwrap()).clone();
    // Sort by due date
    ret_vec.sort_by(|lhs, rhs| { lhs.due_date.cmp(&rhs.due_date) });
    // Return the description vector
    ret_vec
      .into_iter()
      .map(|x| x.description)
      .collect()
  }

  fn get_tasks_for_tag(&self, user_id: i32, tag: String) -> Vec<String> {
    if
      !self.user_map.contains_key(&user_id) ||
      self.user_map.get(&user_id).unwrap().is_empty()
    {
      return vec![];
    }
    // Get the task vector
    let mut ret_vec = (*self.user_map.get(&user_id).unwrap()).clone();
    // Sort by due date
    ret_vec.sort_by(|lhs, rhs| { lhs.due_date.cmp(&rhs.due_date) });
    // Return the description vector
    ret_vec
      .into_iter()
      .filter(|x| x.tags.contains(&tag))
      .map(|x| x.description)
      .collect()
  }

  fn complete_task(&mut self, user_id: i32, task_id: i32) {
    if
      !self.user_map.contains_key(&user_id) ||
      self.user_map.get(&user_id).unwrap().is_empty()
    {
      return;
    }
    self.user_map
      .get_mut(&user_id)
      .unwrap()
      .retain(|x| (*x).task_id != task_id);
  }
}