2050. 并行课程 III (opens new window)

1.哈希+记忆化搜索

分析：本题的并行上课数并没有限制，因此当前课程的前置都完成后就可以开始学习。

• 保存每个节点的前驱集合信息
• 计算出每个节点的最短耗时，它等于所有前驱的最大耗时加上当前节点的耗时。这里采用记忆化搜索实现。
• 最终结果保证至少所有节点都执行完毕，因此它等于所有节点耗费时长的最大值。

class Solution {
    Map<Integer,List<Integer>> map=new HashMap<>();
    int[] nodeTime;
    public int minimumTime(int n, int[][] relations, int[] time) {
        nodeTime=new int[n];
        //初始化拓扑排序关系
        for(int i=0;i<relations.length;i++){
            if(!map.containsKey(relations[i][1]-1)) map.put(relations[i][1]-1,new ArrayList<>());
            map.get(relations[i][1]-1).add(relations[i][0]-1);
        }
        //计算完成每个节点的最小耗时
        for(int i=0;i<n;i++){
            if(nodeTime[i]==0) dfs(time,i);
        }
        //汇总最少耗时
        int max=0;
        for(int i=0;i<n;i++){
            max=Math.max(max,nodeTime[i]);
        }
        return max;
    }
    public int dfs(int[] time,int index){
        if(nodeTime[index]!=0) return nodeTime[index];
        if(!map.containsKey(index)){
            return nodeTime[index]=time[index];
        }
        List<Integer> list=map.get(index);
        int max=0;
        for(int i=0;i<list.size();i++){
            max=Math.max(max,dfs(time,list.get(i)));
        }
        return nodeTime[index]=max+time[index];
    }
}