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 <= 105events[i].length == 31 <= startTimei <= endTimei <= 1091 <= valuei <= 106The goal of #2054 Two Best Non-Overlapping Events is to select at most two events that do not overlap in time while maximizing the total value. A key observation is that once events are sorted by start or end time, we can efficiently determine which events can be paired together.
A common approach is to sort events by start time and use binary search to find the next event whose start time is greater than the current event's end time. By precomputing the maximum value from the remaining suffix, we can quickly combine the current event’s value with the best possible future event.
Another strategy uses a priority queue (heap) while iterating through events sorted by start time. As events end, we update the best completed value so far and combine it with the current event.
Both approaches rely on sorting plus efficient lookups, leading to a time complexity around O(n log n) with O(n) additional space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sorting + Binary Search + Suffix Maximum | O(n log n) | O(n) |
| Sorting + Priority Queue (Heap) | O(n log n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
How can sorting the events on the basis of their start times help? How about end times?
How can we quickly get the maximum score of an interval not intersecting with the interval we chose?
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Sorting helps process events in chronological order so that overlapping relationships become easier to evaluate. Once sorted, binary search or heap-based strategies can quickly determine the next compatible event.
Yes, variations of interval scheduling and event selection problems frequently appear in FAANG-style interviews. They test understanding of sorting, greedy thinking, binary search, and efficient data structure usage.
The optimal approach typically involves sorting the events and then using binary search or a heap to find the next compatible event. By combining the current event value with the best possible non-overlapping event, we can efficiently compute the maximum total value in O(n log n) time.
Commonly used data structures include binary search over a sorted array of events and a priority queue (heap). These help quickly identify the next valid non-overlapping event and track the best value seen so far.