当前位置：首页 > news >正文

【LeetCode 算法】Parallel Courses III 并行课程 III-拓扑

news 2025/7/19 6:36:47

文章目录

Parallel Courses III 并行课程 III
- 问题描述：
- 分析
- 代码
- Tag

Parallel Courses III 并行课程 III

问题描述：

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

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

如果一门课的所有先修课都已经完成，你可以在任意时间开始这门课程。
你可以同时上任意门课程。
请你返回完成所有课程所需要的最少月份数。

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

$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\\ 所有的先修课程对 [prevCourse_j, nextCourse_j] 都是互不相同的。\\ time.length == n\\ 1 <= time[i] <= 10^4\\ 先修课程图是一个有向无环图$

分析

该问题的复杂性并不大，是最简单的拓扑问题。

就是必须要有一个固定的顺序来依次的访问，每个课程。问题中也提到不会存在环，而且是一个有向无环图。

同时可以同时学习多门课程，相比较之前的一个问题中，要求一个学期只能选k个课程，条件更加宽松。

所以按照拓扑排序的思路来处理，就是需要构建一个图，图无非就是邻接表或者是邻接矩阵。

但是由于问题的规模限制，邻接表是一个比较合适的选择。

然后进行拓扑排序，同时用 $f [i]$ 记录到达课程i时的最晚时间，而目标是完成所有课程的时候，需要的最少时间，所以要用 $an s$ 记录每个课程的最晚结束时间。

时间复杂度 $O (M + N)$

空间复杂度 $O (M + N)$

代码

拓扑

class Solution {public int minimumTime(int n, int[][] relations, int[] time) {int[] indeg = new int[n+1];List<Integer>[] g = new ArrayList[n+1];for(int i=1;i<=n;i++){g[i] = new ArrayList();}for(int[] re: relations){int from = re[0],to = re[1];indeg[to]++;g[from].add(to);} Queue<Integer> queue = new LinkedList();for(int i=1;i<=n;i++){if(indeg[i]>0) continue;queue.offer(i);}int[] f = new int[n+1];int ans =0;while(!queue.isEmpty()){int idx = queue.poll(); int end = f[idx]+ time[idx-1];ans = Math.max(ans,end);for(int nx: g[idx]){f[nx]= Math.max(f[nx],end);indeg[nx]--;if(indeg[nx]==0){queue.offer(nx);}}} return ans;}
}