1089. Parallel Courses III — Maximum Time with Dependencies

There are n courses labeled 0..n-1. Each edge [a, b] means course a must finish before course b starts, and time[i] is the months course i takes. Courses with satisfied prerequisites run in parallel. Return the minimum months to complete all courses (the longest weighted path through the dependency DAG). The input is JSON {n, edges, time}.

Input: JSON {n, edges, time}.

Output: Integer — the minimum completion time.

Examples

Input: {"n":3,"edges":[[0,2],[1,2]],"time":[3,2,5]}
Output: 8
Explanation: Course 2 waits for the slower prerequisite (3), then +5.

Input: {"n":1,"edges":[],"time":[7]}
Output: 7
Explanation: One course.

Input: {"n":5,"edges":[[0,1],[1,2],[2,3],[3,4]],"time":[1,2,3,4,5]}
Output: 15
Explanation: Sequential chain.

Constraints

• 1<=n<=5*10^4
• directed acyclic

Asked by