#2054

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Two Best Non-Overlapping Events

Maximize the total value of at most two non-overlapping events using state transition dynamic programming efficiently.

array binary search dynamic programming sorting heap priority queue

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.

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.

terminal

Solution

Solution 1: Sorting + Binary Search

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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def maxTwoEvents(self, events: List[List[int]]) -> int:
        events.sort()
        n = len(events)
        f = [events[-1][2]] * n
        for i in range(n - 2, -1, -1):
            f[i] = max(f[i + 1], events[i][2])
        ans = 0
        for _, e, v in events:
            idx = bisect_right(events, e, key=lambda x: x[0])
            if idx < n:
                v += f[idx]
            ans = max(ans, v)
        return ans

Continue Practicing

#2008 maximum earnings from taxi #1851 minimum interval to include each query #2333 minimum sum of squared difference