#2050

Parallel Courses III

expert · 1045 · lc hard +32 · verified · 66.8% accepted · 1,729 likes · top 72%

Description

There are n courses (labeled 1 to n). Prerequisites are given in relations where relations[j] = [prevCourse, nextCourse], and time[i] is the number of months to finish course i+1. You may take any number of courses simultaneously as long as their prerequisites are met. Return the minimum total months to finish all courses (the graph is guaranteed to be a DAG).

Example 1:

Input: n = 3, relations = [[1,3],[2,3]], time = [3,2,5]

Output: 8

Explanation: The figure above represents the given graph and the time required to complete each course.

We start course 1 and course 2 simultaneously at month 0.

Course 1 takes 3 months and course 2 takes 2 months to complete respectively.

Thus, the earliest time we can start course 3 is at month 3, and the total time required is 3 + 5 = 8 months.

Example 2:

Input: n = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]], time = [1,2,3,4,5]

Output: 12

Explanation: The figure above represents the given graph and the time required to complete each course.

You can start courses 1, 2, and 3 at month 0.

You can complete them after 1, 2, and 3 months respectively.

Course 4 can be taken only after course 3 is completed, i.e., after 3 months. It is completed after 3 + 4 = 7 months.

Course 5 can be taken only after courses 1, 2, 3, and 4 have been completed, i.e., after max(1,2,3,7) = 7 months.

Thus, the minimum time needed to complete all the courses is 7 + 5 = 12 months.

Code

1

2

3

class Solution:
    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:

class Solution:
    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int: