Task Dependency Scheduler
MediumGraphs · Snowflake
A pipeline has tasks given as [task_id, duration, dependencies], where dependencies is a list of task ids that must finish before this task can start. Tasks may appear in any order in the list, and any number of tasks can run at the same time.
Every task starts as early as possible: at time 0 if it has no dependencies, otherwise at the latest finish time among its dependencies. Its finish time is its start time plus duration.
Return [task_id, finish_time] for every task, in the same order as the input.
If the dependencies contain a cycle, so some tasks can never start, return an empty list [].
Example 1
- Input:
- tasks = [["deploy", 2, ["test", "build"]], ["build", 4, []], ["test", 3, ["build"]], ["lint", 1, []]]
- Output:
- [["deploy", 9], ["build", 4], ["test", 7], ["lint", 1]]
- Explanation
buildfinishes at 4, sotestruns from 4 to 7.deploywaits for both and runs from 7 to 9.lintis independent and finishes at 1. Results follow the input order.
Example 2
- Input:
- tasks = [["d", 1, ["b", "c"]], ["b", 2, ["a"]], ["c", 5, ["a"]], ["a", 3, []]]
- Output:
- [["d", 9], ["b", 5], ["c", 8], ["a", 3]]
- Explanation
bandcboth start whenafinishes at 3, ending at 5 and 8.dwaits for the later one, so it runs from 8 to 9.
Example 3
- Input:
- tasks = [["a", 1, ["b"]], ["b", 2, ["a"]], ["c", 3, []]]
- Output:
- []
- Explanation
awaits forbandbwaits fora, so neither can start. Because of the cycle the answer is[], even thoughccould run.
Constraints
- 0 ≤
tasks.length≤ 105 - Task ids are distinct non-empty strings, and every dependency id belongs to some task
- The total number of dependencies is at most 2 * 105
- 0 ≤
duration≤ 104