leetcode

commit 8e5b2dfac45e150fefbb5d8eae017f2c7600a385
parent 4cd86f0c533708e9cdb8d461ac2c28608ed6e86f
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 18 Feb 2024 17:17:52 +0000

Daily Problem

Diffstat:
A
Problems/2402.cpp
 | 
44
++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 45 insertions(+), 0 deletions(-)
diff --git a/Problems/2402.cpp b/Problems/2402.cpp
@@ -0,0 +1,44 @@
+class Solution {
+  public:
+    int mostBooked(int n, vector<vector<int>> &meetings) const {
+        sort(begin(meetings), end(meetings));
+
+        typedef pair<long long, int> record;
+        priority_queue<record, vector<record>, greater<>> engaged;
+        priority_queue<int, vector<int>, greater<>> unused;
+        vector<int> count(n);
+
+        for (int i = 0; i < n; i++)
+            unused.push(i);
+
+        for (const auto meeting : meetings) {
+            const int s = meeting[0], e = meeting[1];
+
+            while (!engaged.empty() && engaged.top().first <= s) {
+                unused.push(engaged.top().second);
+                engaged.pop();
+            }
+
+            if (!unused.empty()) {
+                const int room = unused.top();
+                unused.pop();
+
+                count[room] += 1;
+                engaged.push({e, room});
+            } else {
+                const auto [end, room] = engaged.top();
+                engaged.pop();
+
+                count[room] += 1;
+                engaged.push({end + e - s, room});
+            }
+        }
+
+        int maxi = 0;
+        for (int i = 1; i < n; i++) {
+            if (count[i] > count[maxi]) maxi = i;
+        }
+
+        return maxi;
+    }
+};
diff --git a/README.md b/README.md
@@ -1044,6 +1044,7 @@ for solving problems.
 |  2391  |   Medium   | [Minimum Amount of Time to Collect Garbage](Problems/2391.cpp)                                     |
 |  2396  |   Medium   | [Strictly Palindromic Number](Problems/2396.cpp)                                                   |
 |  2397  |   Medium   | [Maximum Rows Covered by Columns](Problems/2397.cpp)                                               |
+|  2402  |    Hard    | [Meeting Rooms III](Problems/2402.cpp)                                                             |
 |  2405  |   Medium   | [Optimal Partition of String](Problems/2405.cpp)                                                   |
 |  2410  |   Medium   | [Maximum Matching of Players With Trainers](Problems/2410.cpp)                                     |
 |  2414  |   Medium   | [Length of the Longest Alphabetical Continuous Substring](Problems/2414.cpp)                       |