Sort the events by end time and use a dynamic programming array to track the best single-event values up to each point. Then, for each event, use binary search to find the last non-overlapping event and combine their values. This approach ensures the sum of at most two non-overlapping events is maximized in optimal time complexity.
Problem Statement
You are given a list of events represented as a 2D array where each event is [startTime, endTime, value]. Each event occupies a continuous time interval and provides a reward value if attended. You may select up to two events to attend, but the events cannot overlap, meaning the second event must start strictly after the first event ends.
Return the maximum sum of values obtainable by attending at most two non-overlapping events. Keep in mind that overlapping at boundary times is disallowed: if one event ends at time t, the next must start at t + 1 or later.
Examples
Example 1
Input: events = [[1,3,2],[4,5,2],[2,4,3]]
Output: 4
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
Choose event 2 for a sum of 5.
Example 3
Input: events = [[1,5,3],[1,5,1],[6,6,5]]
Output: 8
Choose events 0 and 2 for a sum of 3 + 5 = 8.
Constraints
- 2 <= events.length <= 105
- events[i].length == 3
- 1 <= startTimei <= endTimei <= 109
- 1 <= valuei <= 106
Solution Approach
Sort events by end time
Arrange all events in ascending order of end times to allow efficient binary search for the latest non-overlapping event. Sorting enables a structured DP computation.
Dynamic programming with one-event max
Build a DP array where dp[i] stores the maximum value from attending a single event among the first i events. This helps quickly find the best previous event when considering a second event.
Combine two events using binary search
For each event, use binary search to locate the last event that ends before the current event starts. Combine its dp value with the current event's value to evaluate the sum of two non-overlapping events.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(n \cdot \log n) |
| Space | O(n) |
Sorting takes O(n log n), constructing the DP array is O(n), and each binary search is O(log n), yielding overall time complexity O(n log n). Space is O(n) for the DP array.
What Interviewers Usually Probe
- Sorting by end times can simplify non-overlapping checks.
- Using a DP array to store one-event maxima shows clear state transition understanding.
- Binary search integration reveals awareness of combining past results efficiently.
Common Pitfalls or Variants
Common pitfalls
- Failing to account for inclusive end times and start times leading to overlap errors.
- Not storing the best single-event value up to each index, which makes combining events inefficient.
- Attempting a naive O(n^2) comparison between all pairs of events, exceeding time limits.
Follow-up variants
- Maximizing sum for at most k non-overlapping events instead of two.
- Events with weighted durations where value per unit time must be maximized.
- Allowing overlapping events with a penalty to combine values differently.
How GhostInterview Helps
- GhostInterview quickly identifies the DP state transitions relevant to two-event combinations.
- It highlights where binary search can replace nested loops to avoid TLE.
- The tool generates concise examples demonstrating correct non-overlapping selection for debugging logic.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the core pattern for solving Two Best Non-Overlapping Events?
The main pattern is state transition dynamic programming combined with sorting and binary search to efficiently find non-overlapping events.
Why do we sort events by end time rather than start time?
Sorting by end time allows binary search to quickly find the last non-overlapping event for combining maximum values.
Can this approach handle more than two events?
Yes, by extending the DP to track multiple event combinations, though the logic becomes more complex and may require segment trees or k-DP.
How does inclusive time affect event selection?
Inclusive times mean if one event ends at t, the next cannot start at t; it must start at t + 1 or later, which prevents accidental overlap.
What common mistake should I avoid in this problem?
A frequent mistake is checking only start < end instead of accounting for the inclusive boundary rule, leading to invalid overlapping selections.
Need direct help with Two Best Non-Overlapping Events instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Two Best Non-Overlapping Events from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Maximize earnings by optimizing taxi ride selection and tips using array scanning, hash lookups, and sorting.
Open problem page#1851 Minimum Interval to Include Each QueryFind the smallest interval containing each query efficiently using binary search.
Open problem page#2333 Minimum Sum of Squared DifferenceCalculate the minimum sum of squared differences between two arrays using limited modifications and binary search techniques.
Open problem page