1751.cpp (1830B)
1 // Recursive, top down 2 class Solution { 3 typedef vector<int> Event; 4 vector<vector<int>> dp; 5 6 int rec(const vector<Event> &events, const vector<Event>::const_iterator it, int k) { 7 static const auto cmp = [](const Event &a, int val) { return a[0] <= val; }; 8 9 if (!k || it == events.end()) return 0; 10 int idx = distance(events.begin(), it); 11 if (dp[k][idx] != -1) return dp[k][idx]; 12 13 auto next = lower_bound(it, events.end(), (*it)[1], cmp); 14 int with = (*it)[2] + rec(events, next, k - 1); 15 int without = rec(events, it + 1, k); 16 return dp[k][idx] = max(with, without); 17 } 18 19 public: 20 int maxValue(vector<Event> &events, int k) { 21 static const auto cmp = [](const Event &a, const Event &b) { return a[0] < b[0]; }; 22 sort(events.begin(), events.end(), cmp); 23 24 dp = vector(k + 1, vector(events.size(), -1)); 25 return rec(events, events.begin(), k); 26 } 27 }; 28 29 // Iterative, bottom up 30 class Solution { 31 typedef vector<int> Event; 32 33 public: 34 int maxValue(vector<Event> &events, int k) { 35 static const auto cmp = [](const Event &a, int val) { return a[0] <= val; }; 36 static const auto cmp_sort = [](const Event &a, const Event &b) { return a[0] < b[0]; }; 37 sort(events.begin(), events.end(), cmp_sort); 38 39 vector<vector<int>> dp(k + 1, vector(events.size() + 1, 0)); 40 41 auto start = events.rbegin(); 42 for (int i = events.size() - 1; i >= 0; i--, start++) { 43 auto it = lower_bound(start.base(), events.end(), events[i][1], cmp); 44 int offset = distance(events.begin(), it); 45 for (int cnt = 1; cnt <= k; cnt++) { 46 dp[cnt][i] = max(dp[cnt][i + 1], events[i][2] + dp[cnt - 1][offset]); 47 } 48 } 49 50 return dp[k][0]; 51 } 52 };