DSA problem
Two Best Non-Overlapping Events
You are given a 0-indexed 2D integer array of events where events[i] = [startTime_i, endTime_i, value_i]. The i-th event starts at startTime_i and ends at endTime_i, and you gain a value of value_i if you attend it. You can choose at most two non-overlapping events to attend such that the sum of their values is maximized. Two events are non-overlapping when one ends strictly before the other starts — touching at a single time point still counts as overlapping. Return the maximum sum of values you can achieve.
A brute force over all pairs runs in O(n^2), too slow for the constraints. The clever observation is that, when scanning events in start-time order, for any candidate "second event" we only care about the best value among events that have already finished (endTime < currentStart). If we can maintain that "best value of finished events so far" efficiently we get an O(n log n) algorithm.
The data structure that fits perfectly is a min-heap of (endTime, value) pairs, augmented by a running variable maxFinishedValue. Walk through the events in order of increasing start time. For each event, pop every heap entry whose endTime is less than the current startTime, and as you pop each one update maxFinishedValue with its value. The answer for the current event is maxFinishedValue + currentValue (attending the current event plus the best finished one).
After processing every event, also consider attending only one event (or none) by keeping the running maximum. Push the current event's (endTime, value) into the heap before moving on. The total complexity is O(n log n) time and O(n) auxiliary space.
Examples
events = [[1,3,2],[4,5,2],[2,4,3]]4events = [[1,3,2],[4,5,2],[1,5,5]]5events = [[1,5,3],[1,5,1],[6,6,5]]8Constraints
- 2 <= events.length <= 10^5
- events[i].length == 3
- 1 <= startTime_i <= endTime_i <= 10^9
- 1 <= value_i <= 10^6
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.