leetcode

commit c2b2bf3f3dd0e0a998f0a49674e2d4def1348b5e
parent cefb0ade590b17bae2190495e58429b77950d84a
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 11 Oct 2024 11:34:14 +0200

Daily Problem

Diffstat:
A
Problems/1942.cpp
 | 
27
+++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 28 insertions(+), 0 deletions(-)
diff --git a/Problems/1942.cpp b/Problems/1942.cpp
@@ -0,0 +1,27 @@
+class Solution {
+  public:
+    int smallestChair(const vector<vector<int>> &times, int targetFriend) const {
+        static tuple<int, bool, int> timeline[20002];
+        const int n = size(times);
+        priority_queue<int> seats;
+
+        for (int i = 0; i < n; i++) {
+            timeline[i * 2] = {times[i][0], true, i};
+            timeline[i * 2 + 1] = {times[i][1], false, i};
+            seats.push(-i);
+        }
+
+        sort(timeline, timeline + n * 2);
+
+        static int assign[10001];
+        for (const auto [time, sit, person] : span(timeline, timeline + n * 2)) {
+            if (person == targetFriend) return -seats.top();
+            if (sit)
+                assign[person] = seats.top(), seats.pop();
+            else
+                seats.push(assign[person]);
+        }
+
+        return -1;
+    }
+};
diff --git a/README.md b/README.md
@@ -1064,6 +1064,7 @@ for solving problems.
 |  1930  |   Medium   | [Unique Length-3 Palindromic Subsequences](Problems/1930.cpp)                                      |
 |  1934  |   Medium   | [Confirmation Rate](Problems/1934.cpp)                                                             |
 |  1937  |   Medium   | [Maximum Number of Points with Cost](Problems/1937.cpp)                                            |
+|  1942  |   Medium   | [The Number of the Smallest Unoccupied Chair](Problems/1942.cpp)                                   |
 |  1943  |   Medium   | [Describe the Painting](Problems/1943.cpp)                                                         |
 |  1945  |    Easy    | [Sum of Digits of String After Convert](Problems/1945.cpp)                                         |
 |  1947  |   Medium   | [Maximum Compatibility Score Sum](Problems/1947.cpp)                                               |