Parallel Courses III

上课问题, 拓扑排序, 但是这题可以在同一时间连续上课, 然后求最优.

因为可以并行上课, 所以是一道dp问题, dp[i]= max(max(dp[i],dp[i]+time[i]), dp[j]) j is the neighbor of i.

class Solution {
    public int minimumTime(int n, int[][] relations, int[] time) {
        int[] onto = new int[n + 1];
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for(int[] r : relations) {
            onto[r[1]]++;
            Set<Integer> set = map.getOrDefault(r[0], new HashSet<>());
            set.add(r[1]);
            map.put(r[0],set);
        }
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 1; i <= n; i++){
            if(onto[i] == 0)
                queue.add(i);
        }
        int res = 0; 
        int[] dp = new int[n + 1];
        while(!queue.isEmpty()){
            int cur = queue.poll();
            dp[cur] = dp[cur] + time[cur - 1];
            res = Math.max(dp[cur], res);
            for(int cc : map.getOrDefault(cur, new HashSet<>())){
                dp[cc] = Math.max(dp[cc], dp[cur]);
                onto[cc]--;
                if(onto[cc] == 0)
                    queue.add(cc);
            }
        }
        return res; 
    }
}