并行课程 III【LC2050】
给你一个整数
n，表示有n节课，课程编号从1到n。同时给你一个二维整数数组relations，其中relations[j] = [prevCoursej, nextCoursej]，表示课程prevCoursej必须在课程nextCoursej之前 完成（先修课的关系）。同时给你一个下标从 0 开始的整数数组time，其中time[i]表示完成第(i+1)门课程需要花费的 月份 数。请你根据以下规则算出完成所有课程所需要的 最少 月份数：
- 如果一门课的所有先修课都已经完成，你可以在 任意 时间开始这门课程。
- 你可以 同时 上 任意门课程 。
请你返回完成所有课程所需要的 最少 月份数。
**注意：**测试数据保证一定可以完成所有课程（也就是先修课的关系构成一个有向无环图）。
class Solution { public int minimumTime(int n, int[][] relations, int[] time) { List<Integer>[] g = new List[n]; Arrays.setAll(g, e -> new ArrayList<>()); int[] costs = new int[n]; int[] inDeg = new int[n]; Deque<Integer> queue = new LinkedList<>(); // 邻接表 for (int[] relation : relations){ int u = relation[0] - 1, v = relation[1] - 1; g[u].add(v); inDeg[v]++; } // dp计算最少月份数 修完某课程的最少月份数为其先修课的最大时间+其完成需要的时间 // dp[v] = time[v] + max(dp[u]); int res = 0; // 入度 for (int i = 0; i < n; i++){ if (inDeg[i] == 0){ queue.addLast(i); } } // 拓扑排序 while (!queue.isEmpty()){ int u = queue.pollFirst(); costs[u] += time[u]; res = Math.max(res, costs[u]); // order[index++] = u; for (int v : g[u]){ costs[v] = Math.max(costs[v], costs[u]); if (--inDeg[v] == 0){ queue.addLast(v); } } } return res; } }
