Implement Dependency-Aware To-Do List

Problem Description

Design an in-memory dependency-aware to-do list system. Tasks can have directed dependencies: a task cannot be started until all of its prerequisite tasks have been completed.

Implement the DependencyTodoList class with the following methods:

• add_task(task_id: str) -> bool: Adds a new task. Returns True if the task was added successfully. If a task with task_id already exists, returns False.

• add_dependency(task_id: str, prerequisite_id: str) -> bool: Declares that prerequisite_id must be completed before task_id can be worked on. Returns False if:

  • Either task_id or prerequisite_id does not exist.
  • task_id == prerequisite_id (self-dependency).
  • The dependency already exists.
  • Either task has already been completed.
  • Adding this dependency would introduce a cycle. Otherwise, records the dependency and returns True.

• complete_task(task_id: str) -> list[str]: Marks task_id as completed. A task can only be completed if it exists, is not already completed, and all of its prerequisites are already completed. Returns a lexicographically sorted list of task IDs that transitioned to "ready" (i.e., all their prerequisites are now satisfied) as a direct result of completing this task. If task_id cannot be completed, returns an empty list [].

• get_ready_tasks() -> list[str]: Returns a lexicographically sorted list of all task IDs that are currently uncompleted and have all their prerequisites satisfied.

Example

todo = DependencyTodoList()

todo.add_task("design")         # returns True
todo.add_task("code")           # returns True
todo.add_task("test")           # returns True

todo.add_dependency("code", "design")  # returns True: "design" must precede "code"
todo.add_dependency("test", "code")    # returns True: "code" must precede "test"

todo.get_ready_tasks()          # returns ["design"]

# "code" cannot be completed yet because "design" is not completed
todo.complete_task("code")      # returns []

# Completing "design" unblocks "code"
todo.complete_task("design")    # returns ["code"]
todo.get_ready_tasks()          # returns ["code"]

# Completing "code" unblocks "test"
todo.complete_task("code")      # returns ["test"]
todo.complete_task("test")      # returns []
todo.get_ready_tasks()          # returns []

Constraints

• 1 <= len(task_id), len(prerequisite_id) <= 50
• Task IDs consist only of alphanumeric characters and underscores.
• At most 2,000 total calls to all methods combined.
• The total number of unique tasks will not exceed 1,000.