Parallel Courses III Python Solution

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

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

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

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)