{"id":8722,"date":"2021-11-18T19:31:15","date_gmt":"2021-11-19T03:31:15","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8722"},"modified":"2021-11-18T20:00:30","modified_gmt":"2021-11-19T04:00:30","slug":"leetcode-2050-parallel-courses-iii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-2050-parallel-courses-iii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2050. Parallel Courses III"},"content":{"rendered":"\n<p>You are given an integer&nbsp;<code>n<\/code>, which indicates that there are&nbsp;<code>n<\/code>&nbsp;courses labeled from&nbsp;<code>1<\/code>&nbsp;to&nbsp;<code>n<\/code>. You are also given a 2D integer array&nbsp;<code>relations<\/code>&nbsp;where&nbsp;<code>relations[j] = [prevCourse<sub>j<\/sub>, nextCourse<sub>j<\/sub>]<\/code>&nbsp;denotes that course&nbsp;<code>prevCourse<sub>j<\/sub><\/code>&nbsp;has to be completed&nbsp;<strong>before<\/strong>&nbsp;course&nbsp;<code>nextCourse<sub>j<\/sub><\/code>&nbsp;(prerequisite relationship). Furthermore, you are given a&nbsp;<strong>0-indexed<\/strong>&nbsp;integer array&nbsp;<code>time<\/code>&nbsp;where&nbsp;<code>time[i]<\/code>&nbsp;denotes how many&nbsp;<strong>months<\/strong>&nbsp;it takes to complete the&nbsp;<code>(i+1)<sup>th<\/sup><\/code>&nbsp;course.<\/p>\n\n\n\n<p>You must find the&nbsp;<strong>minimum<\/strong>&nbsp;number of months needed to complete all the courses following these rules:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>You may start taking a course at&nbsp;<strong>any time<\/strong>&nbsp;if the prerequisites are met.<\/li><li><strong>Any number of courses<\/strong>&nbsp;can be taken at the&nbsp;<strong>same time<\/strong>.<\/li><\/ul>\n\n\n\n<p>Return&nbsp;<em>the&nbsp;<strong>minimum<\/strong>&nbsp;number of months needed to complete all the courses<\/em>.<\/p>\n\n\n\n<p><strong>Note:<\/strong>&nbsp;The test cases are generated such that it is possible to complete every course (i.e., the graph is a directed acyclic graph).<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><strong><img decoding=\"async\" alt=\"\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/10\/07\/ex1.png\"><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 3, relations = [[1,3],[2,3]], time = [3,2,5]\n<strong>Output:<\/strong> 8\n<strong>Explanation:<\/strong> The figure above represents the given graph and the time required to complete each course. \nWe start course 1 and course 2 simultaneously at month 0.\nCourse 1 takes 3 months and course 2 takes 2 months to complete respectively.\nThus, the earliest time we can start course 3 is at month 3, and the total time required is 3 + 5 = 8 months.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><strong><img decoding=\"async\" alt=\"\" src=\"https:\/\/assets.leetcode.com\/uploads\/2021\/10\/07\/ex2.png\"><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]], time = [1,2,3,4,5]\n<strong>Output:<\/strong> 12\n<strong>Explanation:<\/strong> The figure above represents the given graph and the time required to complete each course.\nYou can start courses 1, 2, and 3 at month 0.\nYou can complete them after 1, 2, and 3 months respectively.\nCourse 4 can be taken only after course 3 is completed, i.e., after 3 months. It is completed after 3 + 4 = 7 months.\nCourse 5 can be taken only after courses 1, 2, 3, and 4 have been completed, i.e., after max(1,2,3,7) = 7 months.\nThus, the minimum time needed to complete all the courses is 7 + 5 = 12 months.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= n &lt;= 5 * 10<sup>4<\/sup><\/code><\/li><li><code>0 &lt;= relations.length &lt;= min(n * (n - 1) \/ 2, 5 * 10<sup>4<\/sup>)<\/code><\/li><li><code>relations[j].length == 2<\/code><\/li><li><code>1 &lt;= prevCourse<sub>j<\/sub>, nextCourse<sub>j<\/sub>&nbsp;&lt;= n<\/code><\/li><li><code>prevCourse<sub>j<\/sub>&nbsp;!= nextCourse<sub>j<\/sub><\/code><\/li><li>All the pairs&nbsp;<code>[prevCourse<sub>j<\/sub>, nextCourse<sub>j<\/sub>]<\/code>&nbsp;are&nbsp;<strong>unique<\/strong>.<\/li><li><code>time.length == n<\/code><\/li><li><code>1 &lt;= time[i] &lt;= 10<sup>4<\/sup><\/code><\/li><li>The given graph is a directed acyclic graph.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Topological Sorting<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(V+E)<br>Space complexity: O(V+E)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {\n    vector<vector<int>> g(n);  \n    for (const auto& r: relations)\n      g[r[0] - 1].push_back(r[1] - 1);    \n    vector<int> t(n, -1);\n    function<int(int)> dfs = [&](int u) {\n      if (t[u] != -1) return t[u];\n      t[u] = 0;\n      for (int v : g[u])\n        t[u] = max(t[u], dfs(v));\n      return t[u] += time[u];\n    };\n    int ans = 0;\n    for (int i = 0; i < n; ++i)\n      ans = max(ans, dfs(i));\n    return ans;\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\nclass Solution:\n  def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:\n    g = [[] for _ in range(n)]\n    for u, v in relations: g[u - 1].append(v - 1)\n    @cache\n    def dfs(u: int) -> int:      \n      return max([dfs(v) for v in g[u]] + [0]) + time[u]\n    return max(dfs(u) for u in range(n))\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given an integer&nbsp;n, which indicates that there are&nbsp;n&nbsp;courses labeled from&nbsp;1&nbsp;to&nbsp;n. You are also given a 2D integer array&nbsp;relations&nbsp;where&nbsp;relations[j] = [prevCoursej, nextCoursej]&nbsp;denotes that course&nbsp;prevCoursej&nbsp;has&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[76],"tags":[77,217,137],"class_list":["post-8722","post","type-post","status-publish","format-standard","hentry","category-graph","tag-graph","tag-hard","tag-topological-sort","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8722","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8722"}],"version-history":[{"count":5,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8722\/revisions"}],"predecessor-version":[{"id":8729,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8722\/revisions\/8729"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8722"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8722"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8722"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}