OJ练习第145题——并行课程 III

力扣链接：2050. 并行课程 III

题目描述

给你一个整数 n ，表示有 n 节课，课程编号从 1 到 n 。同时给你一个二维整数数组 relations ，其中 relations[j] = [prevCoursej, nextCoursej] ，表示课程 prevCoursej 必须在课程 nextCoursej 之前完成（先修课的关系）。同时给你一个下标从 0 开始的整数数组 time ，其中 time[i] 表示完成第 (i+1) 门课程需要花费的月份数。

请你根据以下规则算出完成所有课程所需要的最少月份数：

如果一门课的所有先修课都已经完成，你可以在任意时间开始这门课程。
你可以同时上任意门课程。
请你返回完成所有课程所需要的最少月份数。

注意：测试数据保证一定可以完成所有课程（也就是先修课的关系构成一个有向无环图）。

示例

在这里插入图片描述

Java代码1（记忆化搜索）

在这里插入图片描述

class Solution {
    public int minimumTime(int n, int[][] relations, int[] time) {
        int max = 0;
        List<Integer>[] prev = new List[n + 1];
        for(int i = 0; i <= n; i++) {
            prev[i] = new ArrayList<Integer>();
        }
        for(int[] relation : relations) {
            int x = relation[0], y = relation[1];
            prev[y].add(x);
        }
        Map<Integer, Integer> memo = new HashMap<Integer, Integer>();
        for(int i = 1; i <= n; i++) {
            max = Math.max(max, dp(i, time, prev, memo));
        }
        return max;
    }

    public int dp(int i, int[] time, List<Integer>[] prev, Map<Integer, Integer> memo) {
        if(!memo.containsKey(i)) {
            int cur = 0;
            for(int p : prev[i]) {
                cur = Math.max(cur, dp(p, time, prev, memo));
            }
            cur += time[i - 1];
            memo.put(i, cur);
        }
        return memo.get(i);
    }
}

Java代码2（拓扑排序）

class Solution {
    public int minimumTime(int n, int[][] relations, int[] time) {
        List<Integer>[] m = new List[n];
        int[] in = new int[n];
        for (int[] r : relations) {
            int pre = r[0] - 1;
            int next = r[1] - 1;
            if (m[pre] == null) {
                m[pre] = new ArrayList();
            }
            m[pre].add(next);
            in[next]++;
        }
        Queue<Integer> q = new ArrayDeque();
        for (int i = 0; i < n; i++) {
            if (in[i] == 0) {
                q.offer(i);
            }
        }
        int[] times = new int[n];
        int ans = 0;
        while (!q.isEmpty()) {
            int pre = q.poll();
            times[pre] += time[pre];
            ans = Math.max(ans, times[pre]);
            if (m[pre] == null) {
                continue;
            }
            for (int next : m[pre]) {
                times[next] = Math.max(times[pre], times[next]);
                in[next]--;
                if (in[next] == 0) {
                    q.offer(next);
                }
            }
        }
        return ans;
    }
}