leetcode

commit e9693c551689f7326d12adebcc0239d537f3aa40
parent 63fa2d04497b88d02d5ab0f2f20e4cfe262918ef
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Mon, 15 Apr 2024 17:24:25 +0200

1 Random Problem

Diffstat:
A
Problems/3111.cpp
 | 
21
+++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 22 insertions(+), 0 deletions(-)
diff --git a/Problems/3111.cpp b/Problems/3111.cpp
@@ -0,0 +1,21 @@
+class Solution {
+  public:
+    int minRectanglesToCoverPoints(const vector<vector<int>> &points, int w) const {
+        set<int> st;
+
+        for (const auto &point : points)
+            st.insert(point[0]);
+        if (w == 0) return size(st);
+
+        int res = 1, prev = *st.begin();
+
+        while (true) {
+            auto it = st.upper_bound(prev + w);
+            if (it == st.end()) break;
+            prev = *it;
+            res++;
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -1197,3 +1197,4 @@ for solving problems.
 |  3100  |   Medium   | [Water Bottles II](Problems/3100.cpp)                                                              |
 |  3101  |   Medium   | [Count Alternating Subarrays](Problems/3101.cpp)                                                   |
 |  3106  |   Medium   | [Lexicographically Smallest String After Operations With Constraint](Problems/3106.cpp)            |
+|  3111  |   Medium   | [Minimum Rectangles to Cover Points](Problems/3111.cpp)                                            |