What is each task waiting for?
Decide whether a set of tasks with prerequisites can all be done, by repeatedly finishing whatever has nothing left to wait for. About 15 minutes.
Count what each task waits for
Give every task a number: how many other tasks it is still waiting on. A task with 0 can be done right now. So put all the zeros in a line.
Take a task from the line and do it. Everything that was waiting on it now waits for one fewer thing, so lower each of their counts by 1. Whichever count just hit zero joins the line. Keep going until the line is empty.
waiting = [0] * n # one more it waits for waiting[task] += 1
- done
- 0
- ready
- [0, 1]
Tasks 0 and 1 wait for nothing, so they join the line. Task 2 waits for two, and 3 and 4 wait for one each.
Leftovers mean a circle
When the line empties, count how many tasks got done. If it is every task, there is a valid order and the answer is yes.
If some tasks were never done, each of them is waiting on something that was also never done, so they must be tangled in a circle (or waiting for one). They'd wait forever, and the answer is no. You don't need to find the circle itself.
done += 1
if done == n:
print("no circle")After the line empties, 3 of 5 tasks were done. What does that tell you?
- AThe other 2 wait on each other (or on something stuck), so it can't all be done
- BThe other 2 are fine, they just weren't needed
- CThe counts were wrong somewhere
Show the answer
The other 2 wait on each other (or on something stuck), so it can't all be done. A task only gets done when its waiting count reaches 0, and a stuck group can never get there.
Can you finish every course?
There are n courses numbered 0 to n − 1. prerequisites[i] = [a, b] means you must take course b before course a. Return true if it is possible to take all the courses, and false otherwise.
n = 5, prerequisites = [[2, 0], [2, 1], [3, 2], [4, 1]] → true
1 ≤ n ≤ 100,000 · 0 ≤ prerequisites ≤ 200,000