Minimum Time to Complete Tasks
InterviewTime limit2sMemory limit256 MB
Given tasks with durations and prerequisites forming a DAG (prerequisites always have smaller index), compute the minimum total time to finish all tasks using longest path via DP.
- Level
Medium4 of 10
- Topics
- Dynamic programming, Topological sort, Graph
- Solved
- No attempts yet
Problem
There are N tasks to complete, where 3 <= N <= 10000. Each task has an integer duration between 1 and 100.
Some tasks have prerequisites. A task may start only after all of its prerequisite tasks are complete. For task K, every prerequisite task number is between 1 and K - 1. At least one task has no prerequisites, and task 1 always has none.
Tasks with no prerequisite relationship between them may be performed at the same time. Find the minimum time required to complete all tasks.
Input
The first line contains N, the number of tasks.
The next N lines describe tasks 1 through N in order. Each line first contains the duration of the task, followed by the number C of prerequisite tasks (0 <= C <= 100). It is then followed by the C prerequisite task numbers.
Output
Print one line containing the minimum time required to complete all tasks.
Hint
The finish time of a task is its own duration plus the latest finish time among all of its prerequisites. The total completion time is the maximum finish time among all tasks.