leetcode

commit fb2343cec8a97bf5b6dcef7feb846d3fc2a5a620
parent 51bb8de6006ad899b1ec3adcbe504e9c080fcbf1
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue, 17 Dec 2024 23:20:01 +0100

1 Random Problem

Diffstat:
A
Problems/0732.cpp
 | 
41
+++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 42 insertions(+), 0 deletions(-)
diff --git a/Problems/0732.cpp b/Problems/0732.cpp
@@ -0,0 +1,41 @@
+// Map solution
+class MyCalendarThree {
+    map<int, int> mp;
+
+  public:
+    int book(int startTime, int endTime) {
+        mp[startTime]++;
+        mp[endTime]--;
+
+        int res = 0, acc = 0;
+        for (const auto [_, add] : mp) {
+            res = max(res, acc += add);
+        }
+
+        return res;
+    }
+};
+
+// Vector solution
+class MyCalendarThree {
+    using type_t = pair<int, int>;
+    vector<type_t> vec;
+
+  public:
+    int book(int startTime, int endTime) {
+        const type_t start = {startTime, 1};
+        const type_t end = {endTime, -1};
+
+        // trick to insert into a sorted vector
+        vec.insert(upper_bound(vec.begin(), vec.end(), start), start);
+
+        vec.insert(upper_bound(vec.begin(), vec.end(), end), end);
+
+        int res = 0, acc = 0;
+        for (const auto [_, add] : vec) {
+            res = max(res, acc += add);
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -560,6 +560,7 @@ reference and a base for solving problems.
 |  0726  |    Hard    | [Number of Atoms](Problems/0726.cpp)                                                               |
 |  0729  |   Medium   | [My Calendar I](Problems/0729.cpp)                                                                 |
 |  0731  |   Medium   | [My Calendar II](Problems/0731.cpp)                                                                |
+|  0732  |    Hard    | [My Calendar III](Problems/0732.cpp)                                                               |
 |  0733  |    Easy    | [Flood Fill](Problems/0733.cpp)                                                                    |
 |  0735  |   Medium   | [Asteroid Collision](Problems/0735.cpp)                                                            |
 |  0738  |   Medium   | [Monotone Increasing Digits](Problems/0738.cpp)                                                    |