Minimum Months to Finish All Courses with Durations and Unlimited Parallelism
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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
```python
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**
```text
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**
```text
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**
```text
Input: n = 2, prerequisites = [], time = [7, 4]
Output: 7
```
Both courses run in parallel from month 0.
Overview: Courses take different numbers of months, some must finish before others start, and any number can run in parallel; return the minimum time to finish them all. It tests longest-path reasoning on a directed acyclic graph processed in topological order.
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.
### 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.
Return the answer as a single integer. It is at most `5 * 10^8`, so it never exceeds `2^31 - 1` and fits a 32-bit `int` in Java and C++.
### 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**
```text
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**
```text
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.
Constraints
- 1 <= n <= 5 * 10^4
- 0 <= len(prerequisites) <= 5 * 10^4
- Each pair [course, before] holds two different course numbers between 0 and n - 1, no pair appears twice, and the pairs contain no cycle.
- len(time) == n
- 1 <= time[i] <= 10^4, so the answer is at most 5 * 10^8 (fits a 32-bit signed integer).
Examples
Input: (1, [], [1])
Expected Output: 1
Explanation: Minimum valid: one course with no prerequisites finishes at time[0] = 1.
Input: (3, [[2, 0], [2, 1]], [3, 2, 5])
Expected Output: 8
Explanation: Example 1: course 2 waits for the slower of courses 0 (3) and 1 (2), so 3 + 5 = 8.
Hints
- A course cannot start until every course it waits for is complete, so its completion month depends on the completion months of all of its prerequisites plus its own duration.
- Because the prerequisites contain no cycle, you can settle each course's completion month once the completion months of all its prerequisites are known.
- Every course has to be complete, so think about which course finishes last; it is not necessarily course n - 1.