Hard

题目描述

给你一个整数 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 个月后。它在 3 + 4 = 7 个月后完成。
课程 5 只能在课程 1、2、3 和 4 都完成后开始，即 max(1,2,3,7) = 7 个月后。
因此，完成所有课程的最少时间为 7 + 5 = 12 个月。

约束条件：

  • 1 <= n <= 5 * 10^4
  • 0 <= relations.length <= min(n * (n - 1) / 2, 5 * 10^4)
  • relations[j].length == 2
  • 1 <= prevCoursej, nextCoursej <= n
  • prevCoursej != nextCoursej
  • 所有的 [prevCoursej, nextCoursej] 都是唯一的
  • time.length == n
  • 1 <= time[i] <= 10^4
  • 给定的图是有向无环图

解题思路

这道题是经典的拓扑排序问题，需要考虑课程的依赖关系和完成时间。

核心思想：

  1. 每门课程的最早开始时间取决于其所有先修课程的完成时间的最大值
  2. 课程可以并行进行，所以需要动态规划思想计算每门课程的最早完成时间

解法分析：

  • 拓扑排序 + 动态规划：使用Kahn算法进行拓扑排序，同时维护每门课程的最早完成时间
  • DFS + 记忆化搜索：深度优先搜索计算每门课程的最早完成时间

推荐解法：拓扑排序 + 动态规划

  1. 构建邻接表和入度数组
  2. 将入度为0的课程加入队列，这些课程可以立即开始
  3. 使用BFS进行拓扑排序，对于每个当前课程：
    • 计算其完成时间 = 开始时间 + 课程时长
    • 更新所有后续课程的最早开始时间
    • 将入度变为0的后续课程加入队列
  4. 返回所有课程完成时间的最大值

时间复杂度为O(V+E)，空间复杂度为O(V+E)，其中V是课程数，E是依赖关系数。

代码实现

class Solution {
public:
    int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
        vector<vector<int>> graph(n + 1);
        vector<int> indegree(n + 1, 0);
        vector<int> earliest(n + 1, 0);
        
        // 构建图和计算入度
        for (auto& rel : relations) {
            graph[rel[0]].push_back(rel[1]);
            indegree[rel[1]]++;
        }
        
        queue<int> q;
        // 将入度为0的课程加入队列
        for (int i = 1; i <= n; i++) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }
        
        while (!q.empty()) {
            int course = q.front();
            q.pop();
            
            // 当前课程的完成时间
            earliest[course] += time[course - 1];
            
            // 更新所有后续课程的最早开始时间
            for (int next : graph[course]) {
                earliest[next] = max(earliest[next], earliest[course]);
                indegree[next]--;
                if (indegree[next] == 0) {
                    q.push(next);
                }
            }
        }
        
        return *max_element(earliest.begin() + 1, earliest.end());
    }
};

class Solution:
    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:
        from collections import deque, defaultdict
        
        graph = defaultdict(list)
        indegree = [0] * (n + 1)
        earliest = [0] * (n + 1)
        
        # 构建图和计算入度
        for prev, next_course in relations:
            graph[prev].append(next_course)
            indegree[next_course] += 1
        
        queue = deque()
        # 将入度为0的课程加入队列
        for i in range(1, n + 1):
            if indegree[i] == 0:
                queue.append(i)
        
        while queue:
            course = queue.popleft()
            
            # 当前课程的完成时间
            earliest[course] += time[course - 1]
            
            # 更新所有后续课程的最早开始时间
            for next_course in graph[course]:
                earliest[next_course] = max(earliest[next_course], earliest[course])
                indegree[next_course] -= 1
                if indegree[next_course] == 0:
                    queue.append(next_course)
        
        return max(earliest[1:])

public class Solution {
    public int MinimumTime(int n, int[][] relations, int[] time) {
        var graph = new List<List<int>>();
        var indegree = new int[n + 1];
        var earliest = new int[n + 1];
        
        for (int i = 0; i <= n; i++) {
            graph.Add(new List<int>());
        }
        
        // 构建图和计算入度
        foreach (var rel in relations) {
            graph[rel[0]].Add(rel[1]);
            indegree[rel[1]]++;
        }
        
        var queue = new Queue<int>();
        // 将入度为0的课程加入队列
        for (int i = 1; i <= n; i++) {
            if (indegree[i] == 0) {
                queue.Enqueue(i);
            }
        }
        
        while (queue.Count > 0) {
            int course = queue.Dequeue();
            
            // 当前课程的完成时间
            earliest[course] += time[course - 1];
            
            // 更新所有后续课程的最早开始时间
            foreach (int next in graph[course]) {
                earliest[next] = Math.Max(earliest[next], earliest[course]);
                indegree[next]--;
                if (indegree[next] == 0) {
                    queue.Enqueue(next);
                }
            }
        }
        
        int result = 0;
        for (int i = 1; i <= n; i++) {
            result = Math.Max(result, earliest[i]);
        }
        return result;
    }
}

var minimumTime = function(n, relations, time) {
    const graph = Array.from({length: n + 1}, () => []);
    const indegree = new Array(n + 1).fill(0);
    const earliest = new Array(n + 1).fill(0);
    
    // 构建图和计算入度
    for (const [prev, next] of relations) {
        graph[prev].push(next);
        indegree[next]++;
    }
    
    const queue = [];
    // 将入度为0的课程加入队列
    for (let i = 1; i <= n; i++) {
        if (indegree[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(V + E)
空间复杂度O(V + E)

其中 V 是课程数量 n，E 是依赖关系数量 relations.length。拓扑排序需要遍历所有节点和边各一次。

相关题目