同仁行业网站建设报价,设计新颖的兰州h5制作,wordpress dynamo,找人做的网站 没登录口文章目录 Parallel Courses III 并行课程 III问题描述#xff1a;分析代码拓扑 Tag Parallel Courses III 并行课程 III
问题描述#xff1a;
给你一个整数 n #xff0c;表示有 n 节课#xff0c;课程编号从 1 到 n 。同时给你一个二维整数数组 relations #xff0c;其… 文章目录 Parallel Courses III 并行课程 III问题描述分析代码拓扑 Tag Parallel Courses III 并行课程 III
问题描述
给你一个整数 n 表示有 n 节课课程编号从 1 到 n 。同时给你一个二维整数数组 relations 其中 r e l a t i o n s [ j ] [ p r e v C o u r s e j , n e x t C o u r s e j ] relations[j] [prevCourse_j, nextCourse_j] relations[j][prevCoursej,nextCoursej] 表示课程 p r e v C o u r s e j prevCourse_j prevCoursej 必须在课程 n e x t C o u r s e j nextCourse_j nextCoursej 之前 完成先修课的关系。同时给你一个下标从 0 开始的整数数组 time 其中 t i m e [ i ] time[i] time[i] 表示完成第 ( i 1 ) (i1) (i1) 门课程需要花费的 月份 数。
请你根据以下规则算出完成所有课程所需要的 最少 月份数
如果一门课的所有先修课都已经完成你可以在 任意 时间开始这门课程。 你可以 同时 上 任意门课程 。 请你返回完成所有课程所需要的 最少 月份数。
注意测试数据保证一定可以完成所有课程也就是先修课的关系构成一个有向无环图。 1 n 5 ∗ 1 0 4 0 r e l a t i o n s . l e n g t h m i n ( n ∗ ( n − 1 ) / 2 , 5 ∗ 1 0 4 ) r e l a t i o n s [ j ] . l e n g t h 2 1 p r e v C o u r s e j , n e x t C o u r s e j n p r e v C o u r s e j ! n e x t C o u r s e j 所有的先修课程对 [ p r e v C o u r s e j , n e x t C o u r s e j ] 都是互不相同的。 t i m e . l e n g t h n 1 t i m e [ i ] 1 0 4 先修课程图是一个有向无环图 1 n 5 * 10^4\\ 0 relations.length min(n * (n - 1) / 2, 5 * 10^4)\\ relations[j].length 2\\ 1 prevCourse_j, nextCourse_j n\\ prevCourse_j ! nextCourse_j\\ 所有的先修课程对 [prevCourse_j, nextCourse_j] 都是 互不相同 的。\\ time.length n\\ 1 time[i] 10^4\\ 先修课程图是一个有向无环图 1n5∗1040relations.lengthmin(n∗(n−1)/2,5∗104)relations[j].length21prevCoursej,nextCoursejnprevCoursej!nextCoursej所有的先修课程对[prevCoursej,nextCoursej]都是互不相同的。time.lengthn1time[i]104先修课程图是一个有向无环图
分析 该问题的复杂性并不大是最简单的拓扑问题。 就是必须要有一个固定的顺序来依次的访问每个课程。问题中也提到不会存在环而且是一个有向无环图。
同时可以同时学习多门课程相比较之前的一个问题中要求一个学期只能选k个课程条件更加宽松。
所以按照拓扑排序的思路来处理就是需要构建一个图图无非就是邻接表或者是邻接矩阵。
但是由于问题的规模限制邻接表是一个比较合适的选择。
然后进行拓扑排序同时用 f [ i ] f[i] f[i] 记录到达课程i时的最晚时间而目标是完成所有课程的时候需要的最少时间所以要用 a n s ans ans记录每个课程的最晚结束时间。
时间复杂度 O ( M N ) O(MN) O(MN)
空间复杂度 O ( M N ) O(MN) O(MN)
代码 拓扑
class Solution {public int minimumTime(int n, int[][] relations, int[] time) {int[] indeg new int[n1];ListInteger[] g new ArrayList[n1];for(int i1;in;i){g[i] new ArrayList();}for(int[] re: relations){int from re[0],to re[1];indeg[to];g[from].add(to);} QueueInteger queue new LinkedList();for(int i1;in;i){if(indeg[i]0) continue;queue.offer(i);}int[] f new int[n1];int ans 0;while(!queue.isEmpty()){int idx queue.poll(); int end f[idx] time[idx-1];ans Math.max(ans,end);for(int nx: g[idx]){f[nx] Math.max(f[nx],end);indeg[nx]--;if(indeg[nx]0){queue.offer(nx);}}} return ans;}
}时间复杂度 O ( M N ) O(MN) O(MN)
空间复杂度 O ( M N ) O(MN) O(MN)
Tag
Array
Graph
Topological Sort
