THINK FIRST·CODE LATER

← All labs

Project schedule: the critical path

Problem

A project has n tasks with durations in days, and m dependencies u v meaning "task u must finish before task v starts" (a weighted DAG). Write ProjectSchedule: process the tasks in topological order (Kahn's algorithm with a queue); the earliest start of a task is the latest finish among its prerequisites.

Input: n m, then n lines name duration, then the m dependencies (task numbers from 0). Print each task's start and finish day, the project length and the critical path — the chain of tasks that determines that length. If the dependencies contain a cycle, print The dependencies contain a cycle: no schedule exists.

For the input

6 6
Design 3
Backend 5
Frontend 4
Database 2
Testing 3
Launch 1
0 1
0 2
0 3
1 4
2 4
4 5

the program prints

Design: day 0 to day 3
Backend: day 3 to day 8
Frontend: day 3 to day 7
Database: day 3 to day 5
Testing: day 8 to day 11
Launch: day 11 to day 12
Project length: 12 days
Critical path: Design -> Backend -> Testing -> Launch

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.

d16-6-data-1.txt

6 6
Design 3
Backend 5
Frontend 4
Database 2
Testing 3
Launch 1
0 1
0 2
0 3
1 4
2 4
4 5
What your program must print for d16-6-data-1.txt
Design: day 0 to day 3
Backend: day 3 to day 8
Frontend: day 3 to day 7
Database: day 3 to day 5
Testing: day 8 to day 11
Launch: day 11 to day 12
Project length: 12 days
Critical path: Design -> Backend -> Testing -> Launch

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 < d16-6-data-1.txt

Windows PowerShell does not understand <:

Get-Content d16-6-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.