2590. Design a Todo List π
Description
Design a Todo List Where users can add tasks, mark them as complete, or get a list of pending tasks. Users can also add tags to tasks and can filter the tasks by certain tags.
Implement the TodoList
class:
TodoList()
Initializes the object.int addTask(int userId, String taskDescription, int dueDate, List<String> tags)
Adds a task for the user with the IDuserId
with a due date equal todueDate
and a list of tags attached to the task. The return value is the ID of the task. This ID starts at1
and is sequentially increasing. That is, the first task's id should be1
, the second task's id should be2
, and so on.List<String> getAllTasks(int userId)
Returns a list of all the tasks not marked as complete for the user with IDuserId
, ordered by the due date. You should return an empty list if the user has no uncompleted tasks.List<String> getTasksForTag(int userId, String tag)
Returns a list of all the tasks that are not marked as complete for the user with the IDuserId
and havetag
as one of their tags, ordered by their due date. Return an empty list if no such task exists.void completeTask(int userId, int taskId)
Marks the task with the IDtaskId
as completed only if the task exists and the user with the IDuserId
has this task, and it is uncompleted.
Example 1:
Input ["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]] Output [null, 1, 2, ["Task1", "Task2"], [], 3, ["Task3", "Task2"], null, null, ["Task3"], ["Task3", "Task1"]] Explanation TodoList todoList = new TodoList(); todoList.addTask(1, "Task1", 50, []); // return 1. This adds a new task for the user with id 1. todoList.addTask(1, "Task2", 100, ["P1"]); // return 2. This adds another task for the user with id 1. todoList.getAllTasks(1); // return ["Task1", "Task2"]. User 1 has two uncompleted tasks so far. todoList.getAllTasks(5); // return []. User 5 does not have any tasks so far. todoList.addTask(1, "Task3", 30, ["P1"]); // return 3. This adds another task for the user with id 1. todoList.getTasksForTag(1, "P1"); // return ["Task3", "Task2"]. This returns the uncompleted tasks that have the tag "P1" for the user with id 1. todoList.completeTask(5, 1); // This does nothing, since task 1 does not belong to user 5. todoList.completeTask(1, 2); // This marks task 2 as completed. todoList.getTasksForTag(1, "P1"); // return ["Task3"]. This returns the uncompleted tasks that have the tag "P1" for the user with id 1. // Notice that we did not include "Task2" because it is completed now. todoList.getAllTasks(1); // return ["Task3", "Task1"]. User 1 now has 2 uncompleted tasks.
Constraints:
1 <= userId, taskId, dueDate <= 100
0 <= tags.length <= 100
1 <= taskDescription.length <= 50
1 <= tags[i].length, tag.length <= 20
- All
dueDate
values are unique. - All the strings consist of lowercase and uppercase English letters and digits.
- At most
100
calls will be made for each method.
Solutions
Solution 1: Hash Table + Sorted Set
We use a hash table $tasks$ to record the set of tasks for each user, where the key is the user ID and the value is a sorted set sorted by the deadline of the task. In addition, we use a variable $i$ to record the current task ID.
When calling the addTask
method, we add the task to the task set of the corresponding user and return the task ID. The time complexity of this operation is $O(\log n)$.
When calling the getAllTasks
method, we traverse the task set of the corresponding user and add the description of the unfinished task to the result list, and then return the result list. The time complexity of this operation is $O(n)$.
When calling the getTasksForTag
method, we traverse the task set of the corresponding user and add the description of the unfinished task to the result list, and then return the result list. The time complexity of this operation is $O(n)$.
When calling the completeTask
method, we traverse the task set of the corresponding user and mark the task whose task ID is $taskId$ as completed. The time complexity of this operation is $(n)$.
The space complexity is $O(n)$. Where $n$ is the number of all tasks.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
|