Parallel Courses III
Hard · Graphs · about 25 minutes
Asked at Snowflake, Amazon, Microsoft, Google, CrowdStrike.
Courses are numbered 1..n, and course i lasts time[i - 1] months. Each pair [prev, next] in relations says prev has to finish before next can begin. You can take as many courses at once as you like, and the prerequisites contain no cycles. What is the fewest months needed to complete everything?