Make writing a habit together! This is the fourth day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details

describe

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 (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: 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.
Copy the code

Note:

  • 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.

parsing

Given an integer n, it represents n courses marked 1 through n. A two-dimensional integer array relations is given, where relations[j] = [prevCoursej, nextCoursej] indicates that course prevCoursej must be completed before course nextCoursej. We also give time, an integer array indexed by 0, where time[I] represents how many months it will take to complete (I +1).

The minimum number of months required to complete all courses must be found according to the following rules:

  • If prerequisites are met, you can start the course at any time
  • You can attend any number of classes at once

It can be seen that this problem is to investigate the longest path of directed acyclic graph. The time required for a course A depends on the most time-consuming course B in its previous courses. If T(x) represents the time required for a course, then T(a) = Max (T(b)+time[a]). In addition, we can use the input degree to indicate whether a course has completed all the previous courses. For each determined pre-taken course, the input degree is reduced by one. When it is reduced to 0, it means that the maximum time required for this course can be calculated.

In addition, BFS is generally used to realize topological sorting. At the beginning of the queue, the course with an enrollment degree of 0 is added first, and every time the loop pops up the first course, all its subsequent updates may be updated once. If the enrollment degree of a course is reduced to 0, it indicates that all its pre-taken courses have been finished and can be added to the queue.

answer

class Solution(object):
    def minimumTime(self, n, relations, time):
        """
        :type n: int
        :type relations: List[List[int]]
        :type time: List[int]
        :rtype: int
        """
        nextCourse = [[] for _ in range(n+1)]
        inDegree = [0] * (n+1)
        for a,b in relations:
            nextCourse[a].append(b)
            inDegree[b] += 1
        
        queue = []
        T = [0]*(n+1)
        for i in range(1, n+1):
            if inDegree[i] == 0:
                queue.append(i)
                T[i] = time[i-1]
        result = 0
        while queue:
            cur = queue.pop(0)
            result = max(result, T[cur])
            for n in nextCourse[cur]:
                T[n] = max(T[n], T[cur]+time[n-1])
                inDegree[n] -= 1
                if inDegree[n] == 0:
                    queue.append(n)
        
        return result
        	      
		
Copy the code

The results

Given in the Python online submissions for Parallel Courses III. Submissions in Python online for Parallel Courses III.Copy the code

Original link: leetcode.com/problems/pa…

Your support is my biggest motivation