leetcode

commit 4cd86f0c533708e9cdb8d461ac2c28608ed6e86f
parent 401e1ac01777d2cab3303a6e5f6c1bd7ceb065cc
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 17 Feb 2024 22:09:12 +0000

1 Random Problem

Diffstat:
A
Problems/1642.cpp
 | 
22
++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 23 insertions(+), 0 deletions(-)
diff --git a/Problems/1642.cpp b/Problems/1642.cpp
@@ -0,0 +1,22 @@
+class Solution {
+  public:
+    int furthestBuilding(const vector<int> &heights, int bricks, int ladders) const {
+        const int n = size(heights);
+        priority_queue<int> pq;
+
+        for (int i = 1; i < n; i++) {
+            const int diff = heights[i] - heights[i - 1];
+            if (diff <= 0) continue;
+            if (diff > bricks) {
+                if (ladders-- == 0) return i - 1;
+                if (pq.empty() || pq.top() < diff) continue;
+                bricks += pq.top();
+                pq.pop();
+            }
+            bricks -= diff;
+            pq.push(diff);
+        }
+
+        return n - 1;
+    }
+};
diff --git a/README.md b/README.md
@@ -839,6 +839,7 @@ for solving problems.
 |  1638  |   Medium   | [Count Substrings That Differ by One Character](Problems/1638.cpp)                                 |
 |  1639  |    Hard    | [Number of Ways to Form a Target String Given a Dictionary](Problems/1639.cpp)                     |
 |  1641  |   Medium   | [Count Sorted Vowel Strings](Problems/1641.cpp)                                                    |
+|  1642  |   Medium   | [Furthest Building You Can Reach](Problems/1642.cpp)                                               |
 |  1646  |    Easy    | [Get Maximum in Generated Array](Problems/1646.cpp)                                                |
 |  1647  |   Medium   | [Minimum Deletions to Make Character Frequencies Unique](Problems/1647.cpp)                        |
 |  1653  |   Medium   | [Minimum Deletions to Make String Balanced](Problems/1653.cpp)                                     |