What is the primary algorithm used in Parallel Courses III?

The primary algorithm is topological sorting combined with graph indegree management to determine the optimal course completion order.

How does parallelism affect the course completion time?

Parallelism allows multiple courses to be completed simultaneously once their prerequisites are finished, reducing the overall time needed.

What is the expected time complexity of solving Parallel Courses III?

The time complexity is O(n + e), where n is the number of courses and e is the number of prerequisite relationships.

What is the key challenge in Parallel Courses III?

The key challenge is scheduling courses in a way that respects all prerequisite relationships while minimizing the total completion time.

Can Parallel Courses III be solved using a brute force approach?

While a brute force approach might work for small inputs, it would be inefficient for larger datasets, and topological sorting is necessary for optimal performance.

#2050

Hard

auto_awesome动态·规划

LeetCode 题解工作台

并行课程 III

给你一个整数 n ，表示有 n 节课，课程编号从 1 到 n 。同时给你一个二维整数数组 relations ，其中 relations[j] = [prevCourse j , nextCourse j ] ，表示课程 prevCourse j 必须在课程 nextCourse j 之前完成（先…

数组动态规划图拓扑排序

题目描述

给你一个整数 n ，表示有 n 节课，课程编号从 1 到 n 。同时给你一个二维整数数组 relations ，其中 relations[j] = [prevCourse_j, nextCourse_j] ，表示课程 prevCourse_j 必须在课程 nextCourse_j 之前完成（先修课的关系）。同时给你一个下标从 0 开始的整数数组 time ，其中 time[i] 表示完成第 (i+1) 门课程需要花费的月份数。

请你根据以下规则算出完成所有课程所需要的最少月份数：

如果一门课的所有先修课都已经完成，你可以在任意时间开始这门课程。
你可以同时上 任意门课程 。

请你返回完成所有课程所需要的最少月份数。

注意：测试数据保证一定可以完成所有课程（也就是先修课的关系构成一个有向无环图）。

示例 1:

输入：n = 3, relations = [[1,3],[2,3]], time = [3,2,5]
输出：8
解释：上图展示了输入数据所表示的先修关系图，以及完成每门课程需要花费的时间。
你可以在月份 0 同时开始课程 1 和 2 。
课程 1 花费 3 个月，课程 2 花费 2 个月。
所以，最早开始课程 3 的时间是月份 3 ，完成所有课程所需时间为 3 + 5 = 8 个月。

示例 2：

输入：n = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]], time = [1,2,3,4,5]
输出：12
解释：上图展示了输入数据所表示的先修关系图，以及完成每门课程需要花费的时间。
你可以在月份 0 同时开始课程 1 ，2 和 3 。
在月份 1，2 和 3 分别完成这三门课程。
课程 4 需在课程 3 之后开始，也就是 3 个月后。课程 4 在 3 + 4 = 7 月完成。
课程 5 需在课程 1，2，3 和 4 之后开始，也就是在 max(1,2,3,7) = 7 月开始。
所以完成所有课程所需的最少时间为 7 + 5 = 12 个月。

提示：

1 <= n <= 5 * 10⁴
0 <= relations.length <= min(n * (n - 1) / 2, 5 * 10⁴)
relations[j].length == 2
1 <= prevCourse_j, nextCourse_j <= n
prevCourse_j != nextCourse_j
所有的先修课程对 [prevCourse_j, nextCourse_j] 都是 互不相同 的。
time.length == n
1 <= time[i] <= 10⁴
先修课程图是一个有向无环图。

lightbulb

解题思路

方法一：拓扑排序 + 动态规划

我们首先根据给定的先修课程关系，构建出一个有向无环图，对该图进行拓扑排序，然后根据拓扑排序的结果，使用动态规划求出完成所有课程所需要的最少时间。

我们定义以下几个数据结构或变量：

邻接表 $g$ 存储有向无环图，同时使用一个数组 $indeg$ 存储每个节点的入度；
队列 $q$ 存储所有入度为 $0$ 的节点；
数组 $f$ 存储每个节点的最早完成时间，初始时 $f[i] = 0$ ；
变量 $ans$ 记录最终的答案，初始时 $ans = 0$ ；

当 $q$ 非空时，依次取出队首节点 $i$ ，遍历 $g[i]$ 中的每个节点 $j$ ，更新 $f[j] = \max(f[j], f[i] + time[j])$ ，同时更新 $ans = \max(ans, f[j])$ ，并将 $j$ 的入度减 $1$ ，如果此时 $j$ 的入度为 $0$ ，则将 $j$ 加入队列 $q$ 中；

最终返回 $ans$ 。

时间复杂度 $O(m + n)$ ，空间复杂度 $O(m + n)$ 。其中 $m$ 是数组 $relations$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

class Solution:
    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:
        g = defaultdict(list)
        indeg = [0] * n
        for a, b in relations:
            g[a - 1].append(b - 1)
            indeg[b - 1] += 1
        q = deque()
        f = [0] * n
        ans = 0
        for i, (v, t) in enumerate(zip(indeg, time)):
            if v == 0:
                q.append(i)
                f[i] = t
                ans = max(ans, t)
        while q:
            i = q.popleft()
            for j in g[i]:
                f[j] = max(f[j], f[i] + time[j])
                ans = max(ans, f[j])
                indeg[j] -= 1
                if indeg[j] == 0:
                    q.append(j)
        return ans

speed

复杂度分析

指标	值
时间	O(n + e)
空间	O(n + e)

psychology

面试官常问的追问

外企场景

question_mark
Look for the candidate’s understanding of topological sorting and how it applies to course scheduling.
question_mark
Check if the candidate efficiently handles course dependencies and parallel execution of independent courses.
question_mark
Observe how well the candidate identifies the minimum completion time, factoring in both prerequisites and parallel courses.

warning

常见陷阱

外企场景

error
Failing to correctly implement the topological sort, which can lead to incorrect processing order of courses.
error
Not properly handling parallelism between courses, which can result in unnecessarily long completion times.
error
Forgetting to calculate the total time based on the prerequisites of each course, leading to incorrect results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Add a constraint where some courses must be completed before others in a cycle, testing the ability to handle cycles in the graph.
arrow_right_alt
Modify the problem to include more dynamic scheduling conditions, such as time constraints for each course based on external factors.
arrow_right_alt
Change the problem to consider weighted prerequisites where different prerequisite courses have different times affecting the start times.

help

常见问题

外企场景

继续练习

#2328 网格图中递增路径的数目 #1728 猫和老鼠 II #2115 从给定原材料中找到所有可以做出的菜