Watch 10 video solutions for Two Best Non-Overlapping Events, a medium level problem involving Array, Binary Search, Dynamic Programming. This walkthrough by codestorywithMIK has 14,494 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |