leetcode

commit 70656d2236524f7148831eb27ce1e6a670bd4358
parent e275d21fb0f091fd5b1fb683a1d92d05802b5881
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Wed, 18 Oct 2023 22:15:17 +0000

Daily Problem

Diffstat:
A
Problems/2050.cpp
 | 
29
+++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 30 insertions(+), 0 deletions(-)
diff --git a/Problems/2050.cpp b/Problems/2050.cpp
@@ -0,0 +1,29 @@
+class Solution {
+  public:
+    int minimumTime(int n, const vector<vector<int>> &relations, const vector<int> &time) {
+        vector<vector<int>> adj(n);
+        vector<int> count(n, 0), wait(n, 0);
+
+        for (const auto &relation : relations) {
+            adj[relation[0] - 1].push_back(relation[1] - 1);
+            count[relation[1] - 1]++;
+        }
+
+        queue<int> q;
+        int res = 0;
+        for (int i = 0; i < n; i++)
+            if (!count[i]) q.push(i);
+        while (!q.empty()) {
+            const int root = q.front();
+            wait[root] += time[root];
+            res = max(res, wait[root]);
+            q.pop();
+            for (const int next : adj[root]) {
+                wait[next] = max(wait[next], wait[root]);
+                if (!--count[next]) q.push(next);
+            }
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -749,6 +749,7 @@ for solving problems.
 |  2039  |   Medium   | [The Time When the Network Becomes Idle](Problems/2039.cpp)                                        |
 |  2043  |   Medium   | [Simple Bank System](Problems/2043.cpp)                                                            |
 |  2044  |   Medium   | [Count Number of Maximum Bitwise-OR Subsets](Problems/2044.cpp)                                    |
+|  2050  |    Hard    | [Parallel Courses III](Problems/2050.cpp)                                                          |
 |  2073  |    Easy    | [Time Needed to Buy Tickets](Problems/2073.cpp)                                                    |
 |  2079  |   Medium   | [Watering Plants](Problems/2079.cpp)                                                               |
 |  2085  |    Easy    | [Count Common Words With One Occurrence](Problems/2085.cpp)                                        |