Free Graphs lessonsGraphs · Stage 4 · Topological order · Step 4

How long does the whole project take?

Give every task a duration, and find the earliest moment everything can be finished when independent work runs in parallel. About 15 minutes.

Waiting for the slowest

Building a house: the walls need the foundation, the roof needs the walls, and the electrics only need the walls too. If the roof takes 5 days and the electrics 3, they can run side by side. Painting can start only when both are finished.

So a task starts at the latest finish among its prerequisites, because it has to wait for the slowest one. Its own finish is then that start plus how long it takes.

Start: equals the latest finish among prerequisites.

Finish: equals start plus its own time.

In code

end = start + duration       # when it ends
# slowest decides
later = max(later, end)

Days each task takes: 0 design (2), 1 materials (5), 2 build (3), 3 test rig (4), 4 launch (1).

finishes: design ends day 2, materials day 5

Design and materials have no prerequisites, so both start on day 0. They finish on day 2 and day 5.

Move 1 of 5

Use the same ready-first order

You can take the tasks in the same ready-first order as before. When a task leaves the line, all its prerequisites have already left, so its start time is final. Work out its finish, then push it forward: for each task that follows, raise its start time to at least this finish.

The answer is the largest finish among all tasks. And if some tasks are never taken, a circle blocks them and the project can never end, so the answer is -1.

Push forward: raise each follower's start to this finish.

Circle: means the project never ends: -1.

In code

best = max(best, finish)

Quick check

A task needs two others: one finishes on day 6, the other on day 9. When can it start?

ADay 9, when the slower one finishes
BDay 6, when the first one finishes
CDay 15, the two finish times added up

Show the answer

Day 9, when the slower one finishes. It needs both, so it waits for the last to finish.

Your problem

Earliest finish

A project has n tasks numbered 0 to n − 1, where durations[i] is how many days task i takes. prerequisites[i] = [a, b] means task b must be finished before task a can start. Any number of tasks can run at the same time. Return the fewest days needed to finish every task, or -1 if the prerequisites contain a circle.

Example

durations = [3, 4, 5, 3, 2], prerequisites = [[1, 0], [2, 1], [3, 1], [4, 2], [4, 3]] → 14

1 ≤ n ≤ 100,000 · 0 ≤ prerequisites ≤ 200,000 · the answer fits in a 32-bit integer

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.