diff options
Diffstat (limited to 'max_num_events_attended2.cpp')
-rw-r--r-- | max_num_events_attended2.cpp | 46 |
1 files changed, 46 insertions, 0 deletions
diff --git a/max_num_events_attended2.cpp b/max_num_events_attended2.cpp new file mode 100644 index 0000000..4c54b9d --- /dev/null +++ b/max_num_events_attended2.cpp @@ -0,0 +1,46 @@ +// 1751. Maximum Number of Events That Can Be Attended II +#include "leetcode.h" + +/* + * given an array of 'events' where 'events[i] = [startdayi, enddayi, valuei]'. + * the i'th event starts at 'startdayi' and ends at 'enddayi', and if you attent + * this event, you will receive a value of 'valuei'. you are also given an + * integer 'k' which represents the maximum number of events you can attend. you + * can only attend one event at a time. if you choose to attend an event, you + * must attend the entire event. note that the end day is inclusive: that is, + * you cannot attend two events where one of them starts and the other ends on + * the same day. return the maximum sum of values that you can receive by + * attending events + */ + +class Solution { + vvd(int) dp; + int dfs(vvd(int) & events, int k, int i) { + if (!k || i >= events.size()) + return 0; + if (dp[i][k] != -1) + return dp[i][k]; + auto j = upper_bound(begin(events) + i, end(events), events[i][1], + [](int t, const vector<int> &v) { return v[0] > t; }) - + begin(events); + return dp[i][k] == + max(events[i][2] + dfs(events, k - 1, j), dfs(events, k, i + 1)); + } + +public: + int maxValue(vvd(int) & events, int k) { + dp = vvd(int)(events.size(), vector<int>(k + 1, -1)); + sort(begin(events), end(events)); + return dfs(events, k, 0); + } +}; + +int main() { + Solution obj; + vvd(int) e1 = {{1, 2, 4}, {3, 4, 3}, {2, 3, 1}}, + e2 = {{1, 2, 4}, {3, 4, 3}, {2, 3, 10}}, + e3 = {{1, 1, 1}, {2, 2, 2}, {3, 3, 3}, {4, 4, 4}}; + printf("%d\n", obj.maxValue(e1, 2)); // expect: 7 + printf("%d\n", obj.maxValue(e2, 2)); // expect: 10 + printf("%d\n", obj.maxValue(e3, 3)); // expect: 9 +} |