The Fastest Study Plan

Hard

A study program has course_count courses numbered from 1 to course_count. Course i takes durations[i - 1] months. Some courses can only start after others: a pair [a, b] in prereqs means course a must be finished before course b begins. A course can start at any moment once all the courses it depends on are done, and any number of courses can run at the same time. Return the minimum number of months needed to finish the whole program. The dependencies contain no cycles.

Example 1

course_count=4, prereqs=[[1, 2], [1, 3], [3, 4]], durations=[2, 6, 1, 3] → 8

Course 1 ends after 2 months. Course 2 follows it and ends at 2 + 6 = 8. Courses 3 and 4 end at 2 + 1 + 3 = 6. Everything is done after 8 months.

Example 2

course_count=3, prereqs=[], durations=[4, 9, 2] → 9

There are no dependencies, so all courses run at once and we wait for the longest one: 9 months.

Example 3

course_count=3, prereqs=[[2, 1], [3, 1]], durations=[5, 1, 4] → 9

Constraints

1 ≤ course_count ≤ 5·10⁴
0 ≤ len(prereqs) ≤ min(course_count·(course_count − 1)/2, 5·10⁴)
prereqs[j] = [a, b], 1 ≤ a, b ≤ course_count, a ≠ b
All pairs in prereqs are distinct and the dependencies form no cycle
len(durations) = course_count
1 ≤ durations[i] ≤ 10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Graph Topological Sort Array Dynamic Programming