Parallel Courses III
You are given an integer n, which indicates that there are n courses labeled from 1 to n. You are also given a 2D integer array relations where relations[j] = [prevCoursej, nextCoursej] denotes that course prevCoursej has to be completed before course nextCoursej as a prerequisite relationship. Furthermore, you are given a 0-indexed integer array time where time[i] denotes how many months it takes to complete the (i + 1)^th course.
You must find the minimum number of months needed to complete all the courses following these rules:
- You may start taking a course at any time if the prerequisites are met.
- Any number of courses can be taken at the same time.
Return the minimum number of months needed to complete all the courses.
Note: The test cases are generated such that it is possible to complete every course, i.e., the graph is a directed acyclic graph.
Example 1
Input
n = 3, relations = [[1,3],[2,3]], time = [3,2,5]Output
8Courses 1 and 2 can start at month 0, course 3 can start after course 1 finishes at month 3, so the total time 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
12Courses 1, 2, and 3 can start at month 0, course 4 finishes at month 7, and course 5 starts after month 7 and finishes at month 12.
Constraints
- 1 <= n <= 5 * 10^4
- 0 <= relations.length <= min(n * (n - 1) / 2, 5 * 10^4)
- relations[j].length == 2
- 1 <= prevCoursej, nextCoursej <= n
- prevCoursej != nextCoursej
- All the pairs [prevCoursej, nextCoursej] are unique.
- time.length == n
- 1 <= time[i] <= 10^4
- The given graph is a directed acyclic graph.