Parallel Courses III Python Solution

Tested Python solution for LeetCode 2050 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 2050, Hard. Topics: Array, Dynamic Programming, Graph Theory, Topological Sort, Directed Acyclic Graph. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 18 parametrized pytest cases, and a playground notebook:

lcpy gen -n 2050   # by problem number
lcpy gen -s parallel_courses_iii   # by problem name

​

Problem

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] = [prevCourse_j, nextCourse_j] denotes that course prevCourse_j has to be completed before course nextCourse_j (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).

​

Examples

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

Explanation: 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.

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

Explanation: Courses 1, 2 and 3 run in parallel and finish after 1, 2 and 3 months. Course 4 starts after course 3 and finishes at month 7. Course 5 starts at 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 <= prevCourse_j, nextCourse_j <= n
• prevCourse_j != nextCourse_j
• All the pairs [prevCourse_j, nextCourse_j] are unique.
• time.length == n
• 1 <= time[i] <= 10^4
• The given graph is a directed acyclic graph.

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

from collections import deque


class Solution:
    # Time: O(n + e)
    # Space: O(n + e)
    def minimum_time(self, n: int, relations: list[list[int]], time: list[int]) -> int:
        adj: list[list[int]] = [[] for _ in range(n + 1)]
        indegree = [0] * (n + 1)
        for prev_course, next_course in relations:
            adj[prev_course].append(next_course)
            indegree[next_course] += 1

        finish = [0] * (n + 1)
        queue: deque[int] = deque()
        for course in range(1, n + 1):
            if indegree[course] == 0:
                finish[course] = time[course - 1]
                queue.append(course)

        while queue:
            course = queue.popleft()
            for nxt in adj[course]:
                finish[nxt] = max(finish[nxt], finish[course] + time[nxt - 1])
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    queue.append(nxt)

        return max(finish)

​

Complexity

Time	Space
O(n + e)	O(n + e)

​

Tags

NeetCode All.