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.

Title

Script

Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industry's standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book.

Contrary to popular belief, Lorem Ipsum is not simply random text.

1  >>> a = [1, 2, 3]
2  >>> a[-1]
3  3

Get premium for instant access to all content and solutions