You are given an array of events
where events[i] = [startDayi, endDayi, valuei]
. The ith
event starts at startDayi
and ends at endDayi
, and if you attend 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.
Example 1:
Input: events = [[1,2,4],[3,4,3],[2,3,1]], k = 2 Output: 7 Explanation: Choose the green events, 0 and 1 (0-indexed) for a total value of 4 + 3 = 7.
Example 2:
Input: events = [[1,2,4],[3,4,3],[2,3,10]], k = 2 Output: 10 Explanation: Choose event 2 for a total value of 10. Notice that you cannot attend any other event as they overlap, and that you do not have to attend k events.
Example 3:
Input: events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3 Output: 9 Explanation: Although the events do not overlap, you can only attend 3 events. Pick the highest valued three.
Constraints:
1 <= k <= events.length
1 <= k * events.length <= 106
1 <= startDayi <= endDayi <= 109
1 <= valuei <= 106
Solution: DP + Binary Search
Sort events by ending time.
dp[i][j] := max value we can get by attending at most j events among events[0~i].
dp[i][j] = max(dp[i – 1][j], dp[p][j – 1] + value[i])
p is the first event that does not overlap with the current one.
Time complexity: O(nlogn + nk)
Space complexity: O(nk)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// Author: Huahua class Solution { public: int maxValue(vector<vector<int>>& events, int k) { const int n = events.size(); vector<vector<int>> dp(n + 1, vector<int>(k + 1)); vector<int> e(n); auto comp = [](const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; }; sort(begin(events), end(events), comp); for (int i = 1; i <= n; ++i) { const int p = lower_bound(begin(events), begin(events) + i, vector<int>{0, events[i - 1][0], 0}, comp) - begin(events); for (int j = 1; j <= k; ++j) dp[i][j] = max(dp[i - 1][j], dp[p][j - 1] + events[i - 1][2]); } return dp[n][k]; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment