Task Scheduling 2

Prereq: Topological Sort

This problem extends Task Scheduling. Each task now has a duration, where times[i] is how long tasks[i] takes.

You can run any number of tasks in parallel, as long as dependencies are respected. If [a, b] appears in requirements, task a must finish before task b can start.

There is guaranteed to be a solution.

Examples

Example 1

Input:

tasks = ["a", "b", "c", "d"]
times = [1, 1, 2, 1]
requirements = [["a", "b"], ["c", "b"], ["b", "d"]]

Output: 4

Figure

The longest dependency chain is c -> b -> d, so the minimum total time is 2 + 1 + 1 = 4.

Try it yourself

Solution

Use Kahn's Algorithm, but track completion times while processing the graph.

Let dis[x] be the earliest time task x can finish. For tasks with no prerequisites, dis[x] = time[x] because they can start immediately.

When we process an edge x -> y, task y may need to wait for x, so we update: dis[y] = max(dis[y], dis[x] + time[y]). The max is the key detail. A task can have multiple prerequisites, and it can only start after the slowest prerequisite chain finishes.

The final answer is the maximum value in dis, which is the total time needed to finish all tasks.

Time Complexity: O(n+m)

We process each task once and each dependency edge once.

Space Complexity: O(n)

We store the queue, indegree map, and completion-time map, each proportional to the number of tasks.