There are numCourses courses (0 .. numCourses-1). Each prerequisite a,b means
course b must be taken before course a. If you can take any number of courses per
semester (subject to prerequisites), return the minimum number of semesters needed
to take them all. The prerequisites form a DAG (a directed acyclic graph — no cycles,
so the dependencies can always be satisfied in some order).
semestersRequired(numCourses, prereqs)
This equals the number of courses on the longest prerequisite chain.
Input format: n | edges, edges as a,b course-number pairs.
3 courses, prereqs (0,1)(1,2) // → 3 (2 → 1 → 0)
4 courses, prereqs (1,0)(2,0)(3,1)(3,2) // → 3
2 courses, no prereqs // → 1
This looks like scheduling, but reduces to something familiar: since you can take unlimited courses per semester once prerequisites are satisfied, only a chain of dependencies forces spreading across semesters. Courses that don't depend on each other, even indirectly, can run in parallel. So the minimum semesters equals the length of the longest prerequisite chain — that chain can't be compressed, and everything else slots alongside it for free.
A course's "depth" is the number of courses in the longest chain ending at it, including itself. No prerequisites means depth 1. With prerequisites, depth is 1 plus the max depth among them — you wait for the slowest prerequisite, then take this course the next semester.
The answer is the maximum depth across all courses.
Multiple courses can share the same deep prerequisite — two unrelated later courses both depending on the same foundational one. A naive implementation recomputes that foundational course's depth every time a different chain reaches it, even though depth is fixed regardless of who's asking.
A course's depth depends only on itself and its direct prerequisites. Cache from course to depth. Check before recursing; otherwise compute 1 plus the max depth among prerequisites (or 1 if none), cache, return.
Since prerequisites form a DAG, the recursion terminates, and every course's depth is computed once at cost proportional to its direct prerequisites — O(V + E) total, instead of recomputing shared chains repeatedly.
def semesters_required(num_courses, prereqs):
graph = {i: [] for i in range(num_courses)}
for a, b in prereqs:
graph[a].append(b)
memo = {}
def depth(c):
if c in memo:
return memo[c]
best = 1
for pre in graph.get(c, []):
d = 1 + depth(pre)
if d > best:
best = d
memo[c] = best
return best
overall = 0
for i in range(num_courses):
d = depth(i)
if d > overall:
overall = d
return overall
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.