Minimum Months to Finish All Courses with Durations and Unlimited Parallelism

Courses are numbered 0 to n - 1. Course i takes time[i] months to complete, some courses can start only after others are complete, and any number of courses can be in progress at the same time. Return the minimum number of months needed to complete every course.

Function Signature

def min_completion_time(n: int, prerequisites: list[list[int]], time: list[int]) -> int:

Rules

• Each pair [course, before] in prerequisites means that course course can start only after course before is complete.
• A course with no prerequisites can start at month 0. Any other course can start as soon as its last prerequisite is complete. Once started, course i is complete exactly time[i] months later.
• There is no limit on how many courses run at the same time.
• The prerequisites contain no cycle, so every course can be completed.

Constraints

• 1 <= n <= 5 * 10^4
• 0 <= len(prerequisites) <= 5 * 10^4
• Each pair holds two different course numbers between 0 and n - 1, no pair appears twice, and the pairs contain no cycle.
• len(time) == n and 1 <= time[i] <= 10^4, so the answer is at most 5 * 10^8.

Examples

Example 1

Input: n = 3, prerequisites = [[2, 0], [2, 1]], time = [3, 2, 5]
Output: 8

Courses 0 and 1 start at month 0 and are complete at months 3 and 2. Course 2 starts at month 3 and is complete at month 8.

Example 2

Input: n = 4, prerequisites = [[1, 0], [2, 1], [3, 0]], time = [2, 3, 4, 10]
Output: 12

The chain 0, 1, 2 holds the most courses but is complete at month 2 + 3 + 4 = 9. The chain 0, 3 is complete at month 2 + 10 = 12.

Example 3

Input: n = 2, prerequisites = [], time = [7, 4]
Output: 7

Both courses run in parallel from month 0.