You are given a 0-indexed 2D integer array of events where events[i] = [startTimei, endTimei, valuei]. The ith event starts at startTimeiand 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 <= 105events[i].length == 31 <= startTimei <= endTimei <= 1091 <= 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.
huahualeetcode
Be First to Comment