Writing down the order
Record the order in which tasks become doable, and break ties the same way every time so there is one answer. About 14 minutes.
The order is the record
You already know how to finish tasks as they become ready. If you write down each task at the moment you finish it, the list you end up with is a valid order: every task appears after everything it waits for.
That is all a topological order is. It is not a new algorithm, just the same process with a notebook. And if the notebook ends up shorter than the number of tasks, there was a circle, so no order exists.
One answer from many
With several tasks ready at once, any pick is fine, so many orders are valid. For a problem with one correct output, we add a rule: among the ready tasks, always take the smallest number.
A plain line doesn't do that, because it hands out tasks in the order they arrived. Use a heap, which always gives back its smallest item. Put the zero-waiting tasks in the heap, pop the smallest, and push newly freed tasks as before.
ready = [3, 1, 2] heapify(ready) first = heappop(ready) # 1
- order
- []
- ready
- [3]
Only task 3 waits for nothing, so the heap holds just 3.
Two tasks are ready, 5 and 2. Which does the smallest-first rule pick?
- A2, because it is the smaller number
- B5, because it came first in the list
- CEither, since both are correct
Show the answer
2, because it is the smaller number. The rule only looks at the number, not at when the task became ready.
Course order
There are n courses numbered 0 to n − 1. prerequisites[i] = [a, b] means you must take course b before course a. Return an order in which you could take all the courses. Many orders can be valid, so always choose the smallest-numbered course among those you can take at that moment. If it is impossible to take every course, return an empty list.
n = 5, prerequisites = [[1, 3], [2, 3], [0, 1], [0, 2], [4, 2]] → [3, 1, 2, 0, 4]
1 ≤ n ≤ 100,000 · 0 ≤ prerequisites ≤ 200,000