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:

tasks = ["a", "b", "c", "d"]
requirements = [["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.