Prereq: Topological Sort
For this problem, given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Each requirement will be in the form of a list
a needs to be completed first before task
b can be completed,
There is guaranteed to be a solution.
1tasks = ["a", "b", "c", "d"] 2requirements = [["a", "b"], ["c", "b"], ["b", "d"]]
["a", "c", "b", "d"]
Try it yourself
Apply Kahn's Algorithm to solve the problem.
The time complexity is equal to
n the number of nodes in the graph plus
m the number of edges in the graph.
This is because we have to go through every connection and node once when we sort the graph.
The queue holds at most
n nodes in the worst case.