Compute total time to finish all courses

Problem

You are given n courses labeled 1..n. Each course i takes time[i] units of time to complete.

You are also given prerequisite relations prereqs, where each pair [a, b] means course a must be completed before course b can be taken.

Courses are taken in batches (rounds/semesters) under the following rule:

• At the start of a batch, you may start any number of courses whose prerequisites are already satisfied.
• The batch finishes only when all courses started in that batch finish .
• The duration of a batch is therefore max(time[c]) over all courses c taken in that batch.
• You can only start the next batch after the current batch finishes.

Task

Return the minimum total time required to finish all courses.

Cycle condition

If the prerequisite graph contains a cycle (so it is impossible to finish all courses), return -1.

Example

Suppose prerequisites imply two batches: first take courses {1, 3}, then take {2, 4} (e.g., edges 1 -> 2 and 3 -> 4).

• time = [1, 10, 10, 1] for courses 1..4
• Batch 1 duration: max(1, 10) = 10
• Batch 2 duration: max(10, 1) = 10
• Total = 20

Follow-up (variant scheduling rule)

How would your approach change if courses can start immediately when their prerequisites are satisfied, without waiting for the rest of the current batch to finish (i.e., no batch barrier; courses can overlap asynchronously)? In that variant, return the minimum total completion time or -1 if a cycle exists.

Constraints (typical)

• 1 <= n <= 2 * 10^5
• 0 <= prereqs.length <= 2 * 10^5
• 1 <= time[i] <= 10^9