Task Scheduling

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, b], where task a needs to be completed first before task b can be completed,

There is guaranteed to be a solution.

Examples

Example 1

Input:

1tasks = ["a", "b", "c", "d"]
2requirements = [["a", "b"], ["c", "b"], ["b", "d"]]

Output: ["a", "c", "b", "d"]

Try it yourself

Solution

Apply Kahn's Algorithm to solve the problem.

Time Complexity: O(n+m)

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.

Space Complexity: O(n)

The queue holds at most n nodes in the worst case.