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 <= 106Problem Overview: You are given a list of events where each event has a start time, end time, and value. The goal is to attend at most two non-overlapping events such that the total value is maximized. Two events overlap if one starts before the other ends.
Approach 1: Sorting and Binary Search (O(n log n) time, O(n) space)
Sort events by start time. For each event, you want to quickly find the next event that starts strictly after its end time. Binary search makes this possible. First, preprocess the events and build a suffix array where suffixMax[i] stores the maximum value obtainable from any event starting at or after index i. Then iterate through each event and use binary search to locate the first event whose start time is greater than the current event's end. Combine the current event’s value with the best value from the suffix array. The key insight: sorting enables efficient lookups of the next valid event. Time complexity is O(n log n) due to sorting and binary search per event, while space complexity is O(n) for the suffix maximum array.
This approach relies heavily on sorting and indexed lookups over an array. It performs well even when the event list is large because each lookup avoids scanning the remaining events linearly.
Approach 2: Dynamic Programming with Two Pass (O(n log n) time, O(n) space)
This method separates the problem into two directional passes. First, sort events by start time. During the forward pass, compute the best value achievable starting from each position. During the backward pass, evaluate each event as the first event and determine the best compatible second event. Instead of recomputing values repeatedly, maintain a DP structure that tracks the maximum value seen so far. The idea is similar to building prefix and suffix best values, which avoids recomputation.
Binary search is still used to locate the next valid event after the current one, but the DP structure simplifies how results are combined. The algorithm effectively transforms the problem into two subproblems: selecting the first event and then quickly retrieving the best second event. Sorting dominates the runtime, giving O(n log n) time and O(n) space.
Recommended for interviews: The sorting + binary search solution is the most commonly expected answer. It clearly demonstrates understanding of interval problems, efficient lookups, and preprocessing with suffix maximums. Interviewers usually look for the insight that sorting events allows you to locate the next compatible event in log n time instead of scanning linearly.
To 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.
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.
JavaScript
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.
We can sort the events by their start times, and then preprocess the maximum value starting from each event, i.e., f[i] represents the maximum value of choosing one event from the i-th event to the last event.
Then we enumerate each event. For each event, we use binary search to find the first event whose start time is greater than the end time of the current event, denoted as idx. The maximum value starting from the current event is f[idx] plus the value of the current event, which is the maximum value that can be obtained by choosing the current event as the first event. We take the maximum value among all these values.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the number of events.
| 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. |
| Sorting + Binary Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting + Binary Search | O(n log n) | O(n) | Best general solution. Efficient lookup for the next non-overlapping event after sorting. |
| Dynamic Programming (Two Pass) | O(n log n) | O(n) | Useful when structuring the solution as prefix/suffix maximum values using DP. |
Two Best Non-Overlapping Events | Brute Force | Better | Leetcode 2054 | codestorywithMIK • codestorywithMIK • 14,494 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