并行课程 III

/*
 * 思路：
 * 1. 使用拓扑排序找到课程的完成顺序。
 * 2. 创建一个数组存储每个课程的最早完成时间。
 * 3. 对于每门课程，计算所有先修课程完成后再加上当前课程所需的时间。
 * 4. 返回所有课程中最早完成时间的最大值。
 * 5. 使用Java Stream API来处理数据流。
 */

import java.util.*;
import java.util.stream.*;

public class Solution {
    public int minimumTime(int n, int[][] relations, int[] time) {
        Map<Integer, List<Integer>> graph = IntStream.rangeClosed(1, n)
                                                      .boxed()
                                                      .collect(Collectors.toMap(i -> i, i -> new ArrayList<>()));
        int[] inDegree = new int[n + 1];
        Arrays.stream(relations).forEach(relation -> {
            graph.get(relation[0]).add(relation[1]);
            inDegree[relation[1]]++;
        });

        Queue<Integer> queue = IntStream.rangeClosed(1, n)
                                         .filter(i -> inDegree[i] == 0)
                                         .boxed()
                                         .collect(Collectors.toCollection(LinkedList::new));

        int[] earliestTime = IntStream.rangeClosed(1, n)
                                       .map(i -> time[i - 1])
                                       .toArray();

        while (!queue.isEmpty()) {
            int curr = queue.poll();
            graph.get(curr).forEach(next -> {
                earliestTime[next] = Math.max(earliestTime[next], earliestTime[curr] + time[next - 1]);
                if (--inDegree[next] == 0) {
                    queue.offer(next);
                }
            });
        }

        return Arrays.stream(earliestTime).max().getAsInt();
    }
}