2050. 并行课程 III

给你一个整数 n ，表示有 n 节课，课程编号从 1 到 n 。同时给你一个二维整数数组 relations ，其中 relations[j] = [prevCoursej, nextCoursej] ，表示课程 prevCoursej 必须在课程 nextCoursej 之前 完成（先修课的关系）。同时给你一个下标从 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 * 104
• 0 <= relations.length <= min(n * (n - 1) / 2, 5 * 104)
• relations[j].length == 2
• 1 <= prevCoursej, nextCoursej <= n
• prevCoursej != nextCoursej
• 所有的先修课程对 [prevCoursej, nextCoursej] 都是 互不相同 的。
• time.length == n
• 1 <= time[i] <= 104
• 先修课程图是一个有向无环图。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/parallel-courses-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

成功，比较纯粹的拓扑排序

 方法：拓扑排序

1. 基本结构就是拓扑的做法：

        - 构建图，建立图的映射关系，此题编号从1开始，所以编号要减一

        - 算入度，记录每个点的入度

        - 零入队，入度为零的点入队，用于BFS

        - 无加入, 每次入队后搜索下一个链接点，减少对应点的入度，下一个节点入度为0后，可以入队

2. 处理时间。当所有先修课程完成，才可以修后面的课程。也就是后面课程的开始时间，是由前面课程的最晚结束时间决定的，求得前驱节点的最晚结束时间，就是当前课程的开始时间。时间可以使用数组进行记录，记录节点可以是每个节点的开始时间，也可以是每个节点的结束时间，我这里计入的是结束时间

class Solution {
    public int minimumTime(int n, int[][] relations, int[] time) {
        List[] graph = new List[n];
        Arrays.setAll(graph,o->new ArrayList<>());
        int[] indegree = new int[n];
        for(int[] relation:relations){
            int a = relation[0]-1;
            int b = relation[1]-1;
            indegree[b]++;
            graph[a].add(b);
        }
 
        Queue queue = new LinkedList<>();
        int[] maxEnd = new int[n];
        for(int i = 0; i < n; i++){
            if(indegree[i]==0) {
                queue.offer(i);
                maxEnd[i]=time[i];
            }
        }
 
        int ans = 0;
        while (!queue.isEmpty()){
            int top = queue.poll();
            ans = Math.max(maxEnd[top],ans);
            for(Integer next:graph[top]){
                indegree[next]--;
                maxEnd[next] = Math.max(maxEnd[top]+time[next],maxEnd[next]);
                if(indegree[next]==0) queue.offer(next);
            }
        }
        return ans;
    }
}