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 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≤n≤5×104 0≤ relations.length
≤min(n⋅(n−1)/2,5×104) relations[j].length
=2 1≤prevCoursej ,nextCoursej≤n prevCoursej=nextCoursej All pairs
prevCoursej ,nextCoursej are unique.time.length
=n 1≤ time[i]
≤104 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:
Construct the dependency graph from the
relations
list and use an in-degree counter to keep track of each course’s prerequisites.Enqueue every course with zero in-degree (no prerequisites) and process them in topological order.
As you visit each course, update its completion time by taking the maximum of all its prerequisites’ finish times plus its duration.
Continue until all courses are processed, then return the largest completion time across every course.
Now, let’s look at the solution steps below:
Initialize data structures:
We create an
in_degree
array of sizen + 1
, initialized to0
, to count the number of prerequisites each course has.We also create an adjacency list
adj
of sizen + 1
, whereadj[u]
will hold all courses that depend directly on courseu
.
Populate the graph:
Next, we iterate over each pair
[u, v]
inrelations
.For each pair, we add an edge from
u
tov
by doingadj[u].push_back(v)
and incrementin_degree[v]
to record thatv
has one more prerequisite.
Initialize the queue and completion times:
We create a queue
q
.We also create a
dp
array of sizen+1
to record the earliest finish time for each course.For each course
i
from1
ton
, ifin_degree[i]
is zero (no prerequisites), setdp[i] = time[i-1]
, and pushi
ontoq
.
Process courses in topological order:
While the queue is not empty:
We pop the front course
u
.For every dependent course
v
inadj[u]
:We update
dp[v]
tomax(dp[v], dp[u] + time[v-1])
, since you can only startv
after finishingu
.We decrement
in_degree[v]
. If it becomes zero, pushv
onto the queue, as all its prerequisites are now satisfied.
Compute the final answer:
After the loop, every course’s
dp[i]
holds the earliest month when coursei
finishes.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: