leetcode

commit 05c8686ed873950ead89360be22fbfb967f6ec82
parent 42b1e770bb8cebedeaf32d75ce6cd006b8bb7e3f
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sat, 15 Jul 2023 12:08:54 +0200

Daily Problem

Diffstat:
A
Problems/1751.cpp
 | 
57
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 58 insertions(+), 0 deletions(-)
diff --git a/Problems/1751.cpp b/Problems/1751.cpp
@@ -0,0 +1,57 @@
+// Recursive, top down
+class Solution {
+  typedef vector<int> Event;
+  vector<vector<int>> dp;
+
+  int rec(const vector<Event> &events, const vector<Event>::const_iterator it,
+          int k) {
+    static const auto cmp = [](const Event &a, int val) { return a[0] <= val; };
+
+    if (!k || it == events.end()) return 0;
+    int idx = distance(events.begin(), it);
+    if (dp[k][idx] != -1) return dp[k][idx];
+
+    auto next = lower_bound(it, events.end(), (*it)[1], cmp);
+    int with = (*it)[2] + rec(events, next, k - 1);
+    int without = rec(events, it + 1, k);
+    return dp[k][idx] = max(with, without);
+  }
+
+public:
+  int maxValue(vector<Event> &events, int k) {
+    static const auto cmp = [](const Event &a, const Event &b) {
+      return a[0] < b[0];
+    };
+    sort(events.begin(), events.end(), cmp);
+
+    dp = vector(k + 1, vector(events.size(), -1));
+    return rec(events, events.begin(), k);
+  }
+};
+
+// Iterative, bottom up
+class Solution {
+  typedef vector<int> Event;
+
+public:
+  int maxValue(vector<Event> &events, int k) {
+    static const auto cmp = [](const Event &a, int val) { return a[0] <= val; };
+    static const auto cmp_sort = [](const Event &a, const Event &b) {
+      return a[0] < b[0];
+    };
+    sort(events.begin(), events.end(), cmp_sort);
+
+    vector<vector<int>> dp(k + 1, vector(events.size() + 1, 0));
+
+    auto start = events.rbegin();
+    for (int i = events.size() - 1; i >= 0; i--, start++) {
+      auto it = lower_bound(start.base(), events.end(), events[i][1], cmp);
+      int offset = distance(events.begin(), it);
+      for (int cnt = 1; cnt <= k; cnt++) {
+        dp[cnt][i] = max(dp[cnt][i + 1], events[i][2] + dp[cnt - 1][offset]);
+      }
+    }
+
+    return dp[k][0];
+  }
+};
diff --git a/README.md b/README.md
@@ -515,6 +515,7 @@ for solving problems.
 |  1721  |   Medium   | [Swapping Nodes in a Linked List](Problems/1721.cpp)                                             |
 |  1722  |   Medium   | [Minimize Hamming Distance After Swap Operations](Problems/1722.cpp)                             |
 |  1732  |    Easy    | [Find the Highest Altitude](Problems/1732.cpp)                                                   |
+|  1751  |    Hard    | [Maximum Number of Events That Can Be Attended II](Problems/1751.cpp)                            |
 |  1768  |    Easy    | [Merge Strings Alternately](Problems/1768.cpp)                                                   |
 |  1786  |   Medium   | [Number of Restricted Paths From First to Last Node](Problems/1786.cpp)                          |
 |  1791  |    Easy    | [Find Center of Star Graph](Problems/1791.cpp)                                                   |