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 <= 106To maximize the sum of two non-overlapping events, the first step is to sort all events by their end time. With the events sorted, we can iterate through each event and use binary search to find a non-overlapping event with the maximum possible value that starts after the current event ends. This approach allows efficient selection of the second event by leveraging the sorted order.
This solution sorts the events by their end times. It iterates through the events in reverse to keep track of the maximum possible value for the remaining events. A backwards pass through events captures this when we calculate potential non-overlapping pair sums.
Java
Time Complexity: O(n log n) due to sorting and binary search.
Space Complexity: O(n) for storing maximum values array.
This approach uses a dynamic programming-inspired method to solve the problem. It involves a first pass to determine the maximum value from a single event up to each point and a second pass to calculate the maximum possible two-event combination utilizing non-overlapping constraints.
This JavaScript implementation similarly sorts the events array by ending times. It then employs a backward traversal to build up the accessible maximum values for later reference. During a subsequent forward traversal, each event is paired with a succeeding non-overlapping event using binary search methods, maximizing the resultant sums progressively.
Time Complexity: O(n log n), consisting mainly of the sorting and series of binary searches.
Space Complexity: O(n) due to the need for auxiliary storage of maximum values.
| Approach | Complexity |
|---|---|
| Sorting and Binary Search | Time Complexity: O(n log n) due to sorting and binary search. |
| Dynamic Programming with Two Pass | Time Complexity: O(n log n), consisting mainly of the sorting and series of binary searches. |
Non-Overlapping Intervals - Leetcode 435 - Python • NeetCode • 134,480 views views
Watch 9 more video solutions →Practice Two Best Non-Overlapping Events with our built-in code editor and test cases.
Practice on FleetCode