> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Parallel Courses III Python Solution

> Tested Python solution for LeetCode 2050 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 2050, [Hard](/catalog/hard). Topics: [Array](/catalog/topics/array), [Dynamic Programming](/catalog/topics/dynamic-programming), [Graph Theory](/catalog/topics/graph-theory), [Topological Sort](/catalog/topics/topological-sort), Directed Acyclic Graph. [View on LeetCode](https://leetcode.com/problems/parallel-courses-iii/description/).

Generate this problem as a practice environment: tested reference solution, 18 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 2050   # by problem number
lcpy gen -s parallel_courses_iii   # by problem name
```

## Problem

You are given an integer `n`, which indicates that there are `n` courses labeled from `1` to `n`. You are also given a 2D integer array `relations` where `relations[j] = [prevCourse_j, nextCourse_j]` denotes that course `prevCourse_j` has to be completed **before** course `nextCourse_j` (prerequisite relationship). Furthermore, you are given a **0-indexed** integer array `time` where `time[i]` denotes how many **months** it takes to complete the `(i+1)th` course.

You must find the **minimum** number of months needed to complete all the courses following these rules:

* You may start taking a course at **any time** if the prerequisites are met.
* **Any number of courses** can be taken at the **same time**.

Return *the **minimum** number of months needed to complete all the courses*.

**Note:** The test cases are generated such that it is possible to complete every course (i.e., the graph is a directed acyclic graph).

### Examples

![Example 1](https://assets.leetcode.com/uploads/2021/10/07/ex1.png)

```
Input: n = 3, relations = [[1,3],[2,3]], time = [3,2,5]
Output: 8
```

**Explanation:** We start course 1 and course 2 simultaneously at month 0. Course 1 takes 3 months and course 2 takes 2 months to complete respectively. Thus, the earliest time we can start course 3 is at month 3, and the total time required is 3 + 5 = 8 months.

![Example 2](https://assets.leetcode.com/uploads/2021/10/07/ex2.png)

```
Input: n = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]], time = [1,2,3,4,5]
Output: 12
```

**Explanation:** Courses 1, 2 and 3 run in parallel and finish after 1, 2 and 3 months. Course 4 starts after course 3 and finishes at month 7. Course 5 starts at month 7 and finishes at month 12.

### Constraints

* `1 <= n <= 5 * 10^4`
* `0 <= relations.length <= min(n * (n - 1) / 2, 5 * 10^4)`
* `relations[j].length == 2`
* `1 <= prevCourse_j, nextCourse_j <= n`
* `prevCourse_j != nextCourse_j`
* All the pairs `[prevCourse_j, nextCourse_j]` are **unique**.
* `time.length == n`
* `1 <= time[i] <= 10^4`
* The given graph is a directed acyclic graph.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/parallel_courses_iii/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/parallel_courses_iii/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from collections import deque


class Solution:
    # Time: O(n + e)
    # Space: O(n + e)
    def minimum_time(self, n: int, relations: list[list[int]], time: list[int]) -> int:
        adj: list[list[int]] = [[] for _ in range(n + 1)]
        indegree = [0] * (n + 1)
        for prev_course, next_course in relations:
            adj[prev_course].append(next_course)
            indegree[next_course] += 1

        finish = [0] * (n + 1)
        queue: deque[int] = deque()
        for course in range(1, n + 1):
            if indegree[course] == 0:
                finish[course] = time[course - 1]
                queue.append(course)

        while queue:
            course = queue.popleft()
            for nxt in adj[course]:
                finish[nxt] = max(finish[nxt], finish[course] + time[nxt - 1])
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    queue.append(nxt)

        return max(finish)
```

## Complexity

| Time | Space |
| - | - |
| O(n + e) | O(n + e) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.