You are given a 0-indexed 2D integer array of events
where events[i] = [startTimei, endTimei, valuei]
. The ith
event starts at startTimei
and ends at endTimei
, and if you attend this event, you will receive a value of valuei
. You can choose at most two non-overlapping events to attend such that the sum of their values is maximized.
Return this maximum sum.
Note that the start time and end time is inclusive: that is, you cannot attend two events where one of them starts and the other ends at the same time. More specifically, if you attend an event with end time t
, the next event must start at or after t + 1
.
Example 1:
Input: events = [[1,3,2],[4,5,2],[2,4,3]] Output: 4 Explanation: Choose the green events, 0 and 1 for a sum of 2 + 2 = 4.
Example 2:
Input: events = [[1,3,2],[4,5,2],[1,5,5]] Output: 5 Explanation: Choose event 2 for a sum of 5.
Example 3:
Input: events = [[1,5,3],[1,5,1],[6,6,5]] Output: 8 Explanation: Choose events 0 and 2 for a sum of 3 + 5 = 8.
Constraints:
2 <= events.length <= 105
events[i].length == 3
1 <= startTimei <= endTimei <= 109
1 <= valuei <= 106
Solution: Sort + Heap
Sort events by start time, process them from left to right.
Use a min heap to store the events processed so far, a variable cur to track the max value of a non-overlapping event.
For a given event, pop all non-overlapping events whose end time is smaller than its start time and update cur.
ans = max(val + cur)
Time complexity: O(nlogn)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua class Solution { public: int maxTwoEvents(vector<vector<int>>& events) { using E = pair<int,int>; sort(begin(events), end(events)); priority_queue<E, vector<E>, greater<E>> q; // (end_time, val) int ans = 0; int cur = 0; for (const auto& e : events) { while (!q.empty() && q.top().first < e[0]) { cur = max(cur, q.top().second); q.pop(); } ans = max(ans, cur + e[2]); q.emplace(e[1], e[2]); } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment