THINK FIRST·CODE LATER

← All labs

Critical path finder

Problem

Find the critical path of a task network.

Input: first line n; then n lines TASK duration dep1,dep2,... (or - for no dependencies). Tasks may be listed in any order; every dependency is one of the n tasks and there are no cycles.

Compute for each task its earliest finish EF = duration + max(EF of its dependencies) (0 if none). The project duration is the largest EF. The critical path is built backwards: start from the task with the largest EF (first in input order on a tie); repeatedly go to the dependency with the largest EF (first in that task's dependency list on a tie) until a task with no dependencies.

Output:

TASK: EF=x
... (all tasks in input order)
Project duration: D days
Critical path: A -> C -> E -> F
Slack: TASK=s, TASK=s, ...

Slack lists, in input order, every task not on the critical path with its slack, computed as LF − EF, where the latest finish LF of a task is the minimum over its successors of (LF of successor − duration of successor), and D for tasks with no successors. Print Slack: none if all tasks are critical.

Input:

6
A 3 -
B 4 A
C 5 A
D 6 -
E 7 C,D
F 1 B,E

Output:

A: EF=3
B: EF=7
C: EF=8
D: EF=6
E: EF=15
F: EF=16
Project duration: 16 days
Critical path: A -> C -> E -> F
Slack: B=8, D=2

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

s5-3-data-1.txt

6
A 3 -
B 4 A
C 5 A
D 6 -
E 7 C,D
F 1 B,E
What your program must print for s5-3-data-1.txt
A: EF=3
B: EF=7
C: EF=8
D: EF=6
E: EF=15
F: EF=16
Project duration: 16 days
Critical path: A -> C -> E -> F
Slack: B=8, D=2

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < s5-3-data-1.txt

Windows PowerShell does not understand <:

Get-Content s5-3-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.