Rounds of ready tasks
Take everything that's ready at once, as one round, and count how many rounds the whole job needs. About 14 minutes.
Everything ready, all at once
Imagine you can take any number of courses in a semester, as long as their prerequisites are done in earlier semesters. What is the fewest semesters to finish everything?
Greedy works well here. In each semester take every course that is ready. It never hurts to take a ready course sooner, because nothing is lost by finishing early. Then the freed courses become ready for the next semester.
rounds = 0 rounds += 1 # a whole round at once
- semester
- 1
Semester 1: courses 0 and 1 have no prerequisites, so both are taken together.
Counting the rounds
We have used this trick before: note how many tasks are in the line when a round begins, and process exactly that many. Anything they free joins the line for the next round.
The number of rounds is the answer, provided every course got done. If some were left behind, a circle blocked them and the answer is -1. The count of rounds is also the length of the longest chain, since each round extends it by one.
possible = done == n
A chain of 5 courses, each needing the one before, plus 20 unrelated courses. With unlimited courses per semester, what is the fewest semesters?
- A5, the length of the chain
- B25, one per course
- C20, the number of unrelated courses
Show the answer
5, the length of the chain. The chain needs one semester per link and the unrelated courses fit alongside it.
Fewest semesters
There are n courses numbered 0 to n − 1. prerequisites[i] = [a, b] means you must take course b before course a, in an earlier semester. In one semester you can take any number of courses whose prerequisites are all done. Return the fewest semesters needed to take every course, or -1 if it is impossible.
n = 6, prerequisites = [[2, 0], [2, 1], [3, 2], [4, 2], [5, 4]] → 4
1 ≤ n ≤ 100,000 · 0 ≤ prerequisites ≤ 200,000