专业创业服务平台网站建设需求,国际酒店网站建设不好,免签支付 wordpress,如何建立视频号文章目录1. 题目2. 解题1. 题目
给你一个整数 n #xff0c;表示有 n 节课#xff0c;课程编号从 1 到 n 。 同时给你一个二维整数数组 relations #xff0c;其中 relations[j] [prevCoursej, nextCoursej] #xff0c;表示课程 prevCoursej 必须在课程 nextCoursej 之前…
文章目录1. 题目2. 解题1. 题目
给你一个整数 n 表示有 n 节课课程编号从 1 到 n 。 同时给你一个二维整数数组 relations 其中 relations[j] [prevCoursej, nextCoursej] 表示课程 prevCoursej 必须在课程 nextCoursej 之前 完成先修课的关系。 同时给你一个下标从 0 开始的整数数组 time 其中 time[i] 表示完成第 (i1) 门课程需要花费的 月份 数。
请你根据以下规则算出完成所有课程所需要的 最少 月份数
如果一门课的所有先修课都已经完成你可以在 任意 时间开始这门课程。你可以 同时 上 任意门课程 。
请你返回完成所有课程所需要的 最少 月份数。
注意测试数据保证一定可以完成所有课程也就是先修课的关系构成一个有向无环图。
示例 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 。
在月份 12 和 3 分别完成这三门课程。
课程 4 需在课程 3 之后开始也就是 3 个月后。课程 4 在 3 4 7 月完成。
课程 5 需在课程 123 和 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
先修课程图是一个有向无环图。来源力扣LeetCode 链接https://leetcode-cn.com/problems/parallel-courses-iii 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
拓扑排序入度为0的时候进入队列
class Solution {
public:int minimumTime(int n, vectorvectorint relations, vectorint time) {vectorvectorint g(n);vectorint indegree(n), needtime(n);for (auto re : relations) // 建图{g[re[0]-1].push_back(re[1]-1);indegree[re[1]-1]; // 入度}queueint q;int maxtime 0;for(int i 0; i n; i){if(indegree[i]0){q.push(i);needtime[i] time[i];maxtime max(maxtime, needtime[i]);}}while(!q.empty()){int id q.front();q.pop();for(int nid : g[id]){needtime[nid] max(needtime[nid], needtime[id]time[nid]);maxtime max(maxtime, needtime[nid]);if(--indegree[nid] 0)q.push(nid);}}return maxtime;}
};324 ms 128.5 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
