You are building a workflow scheduler.
Each task has:
-
a unique
task_id
-
an integer
deadline
-
an optional list of prerequisite tasks that must be completed before this task becomes ready
Assume the dependency graph is a DAG.
Implement the scheduler in three stages:
-
Basic version
: Given a list of tasks with no dependencies, return the task with the smallest deadline.
-
Dependency-aware version
: Tasks may have prerequisites. Repeatedly select the currently ready task with the smallest deadline, mark it as completed, and add any newly unlocked tasks to the ready set. Return a valid execution order.
-
Optimized version
: Improve the time complexity of selecting the next ready task by using an efficient data structure instead of scanning the full ready list each time. Analyze the time complexity.
If multiple ready tasks have the same deadline, you may break ties by task_id or return any consistent order.