Solution: Parallel Courses III

Statement  

You are tasked with determining the minimum time required to complete a set of courses, given their prerequisite relationships and individual durations.

There are n courses labeled from 1 to n. The prerequisite relationships between these courses are provided as a 2D integer array relations, where each entry $\text{relations}[j] = [\text{prevCourse}_j, \text{nextCourse}_j]$ indicates that course $\text{prevCourse}_j$ must be completed before course $\text{nextCourse}_j$. An array, time, is also given, where time[i] specifies the number of months required to complete the course labeled i + 1.

You may begin any course as soon as you have completed all its prerequisites. If all the prerequisites are satisfied, multiple courses may be taken simultaneously. Calculate the minimum months needed to finish all the courses.

Note: The given prerequisite structure is guaranteed to form a directed acyclic graph (DAG), ensuring that all courses can be completed.

Constraints:

• $1 \leq n \leq 5 \times 10^4$

• $0 \leq$ relations.length $\leq \min\left(n \cdot (n - 1) / 2, 5 \times 10^4\right)$

• relations[j].length $= 2$

• $1 \leq \text{prevCourse}_j$, $\text{nextCourse}_j \leq n$

• $\text{prevCourse}_j \neq \text{nextCourse}_j$

• All pairs $\text{prevCourse}_j$, $\text{nextCourse}_j$ are unique.

• time.length $= n$

• $1 \leq$ time[i] $\leq 10^4$

• The prerequisite graph is a directed acyclic graph (DAG).

Solution

The essence of this problem lies in managing dependencies between courses, where each course can start only after its prerequisites are finished. Such dependency scheduling naturally maps to a topological sort on a directed acyclic graph (DAG).

We treat each course as a node and draw an edge from U (prerequisite) to V (dependent). Repeatedly removing any “ready” course (in-degree 0) from a queue and recording its finish time gives a valid order. Each time a course finishes, we update every dependent’s earliest finish time, reduce its in-degree, and enqueue it when the in-degree drops to 0. After all courses pass through the queue, the minimum number of months needed for the entire curriculum is the largest recorded finish time.

To solve the problem, we:

1. Construct the dependency graph from the relations list and use an in-degree counter to keep track of each course’s prerequisites.

2. Enqueue every course with zero in-degree (no prerequisites) and process them in topological order.

3. As you visit each course, update its completion time by taking the maximum of all its prerequisites’ finish times plus its duration.

4. Continue until all courses are processed, then return the largest completion time across every course.

Now, let’s look at the solution steps below:

1. Initialize data structures:

   1. We create an in_degree array of size n + 1, initialized to 0, to count the number of prerequisites each course has.

   2. We also create an adjacency list adj of size n + 1, where adj[u] will hold all courses that depend directly on course u.

2. Populate the graph:

   1. Next, we iterate over each pair [u, v] in relations.

   2. For each pair, we add an edge from u to v by doing adj[u].push_back(v) and increment in_degree[v] to record that v has one more prerequisite.

3. Initialize the queue and completion times:

   1. We create a queue q.

   2. We also create a dp array of size n+1 to record the earliest finish time for each course.

   3. For each course i from 1 to n, if in_degree[i] is zero (no prerequisites), set dp[i] = time[i-1], and push i onto q.

4. Process courses in topological order:

   1. While the queue is not empty:

      1. We pop the front course u.

      2. For every dependent course v in adj[u]:

         1. We update dp[v] to max(dp[v], dp[u] + time[v-1]), since you can only start v after finishing u.

         2. We decrement in_degree[v]. If it becomes zero, push v onto the queue, as all its prerequisites are now satisfied.

5. Compute the final answer:

   1. After the loop, every course’s dp[i] holds the earliest month when course i finishes.

   2. The minimum time to finish all courses is the maximum value in dp[1..n]. So we return it.

Let’s look at the following illustration to get a better understanding of the solution: