Problem Description

You are given a list of events where each event has a start time, end time, and value. Each event is represented as [startTime, endTime, value]. Your task is to select at most two non-overlapping events such that the sum of their values is maximized.

Two events are considered overlapping if one event's end time is the same as or after another event's start time. In other words, if you attend an event that ends at time t, the next event you can attend must start at time t + 1 or later.

The goal is to find the maximum possible sum of values you can obtain by attending at most two events. You can choose to attend:

• No events (sum = 0)
• One event (sum = value of that event)
• Two non-overlapping events (sum = value of first event + value of second event)

For example, if you have events [[1,3,4], [3,4,3], [5,6,5]]:

• You cannot attend events [1,3,4] and [3,4,3] together because the first ends at 3 and the second starts at 3 (they overlap)
• You can attend events [1,3,4] and [5,6,5] together for a total value of 9
• You can attend events [3,4,3] and [5,6,5] together for a total value of 8

The function should return the maximum sum achievable, which in this case would be 9.

Intuition

The key insight is that we need to consider each event as a potential "first event" and then find the best possible "second event" that doesn't overlap with it.

If we sort the events by their start times, we can leverage the ordering to efficiently find non-overlapping events. For any event we choose as the first event, we need to find events that start after this event ends.

Here's the thought process:

1. Why sorting helps: Once events are sorted by start time, for any event ending at time e, all valid second events must start at time e + 1 or later. Due to the sorting, these valid events form a contiguous suffix in our sorted array.

2. Precomputation optimization: Instead of checking all possible second events for each first event, we can precompute the maximum value available from each position onwards. If f[i] represents the maximum value of any single event from position i to the end, we can build this array in reverse order: f[i] = max(f[i+1], events[i].value).

3. Binary search for efficiency: For each event ending at time e, we need to find the first event in our sorted array that starts after time e. This is a classic binary search problem - we're looking for the leftmost position where startTime > e.

4. Combining the pieces: For each event with value v:

   • Find the index idx of the first non-overlapping event using binary search
   • If such events exist, the best total value is v + f[idx] (current event's value plus the best value from non-overlapping events)
   • If no non-overlapping events exist, the value is just v
   • Track the maximum across all possibilities

This approach ensures we consider all valid combinations while avoiding the brute force O(n²) comparison of all pairs.

Learn more about Binary Search, Dynamic Programming, Sorting and Heap (Priority Queue) patterns.

Solution Approach

The solution implements the sorting and binary search strategy with precomputation:

Step 1: Sort the events

events.sort()

Events are sorted by start time (first element of each sublist by default). This allows us to use binary search later.

Step 2: Precompute maximum values from each position

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])

• Initialize array f where f[i] will store the maximum value of any single event from index i to the end
• Start with the last event's value for all positions
• Iterate backwards from the second-to-last event, updating f[i] = max(f[i+1], events[i][2])
• This ensures f[i] contains the maximum value achievable from position i onwards

Step 3: Process each event and find the best combination

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)

• For each event with end time e and value v:
  • Use bisect_right to find the first event whose start time is greater than e
  • The key=lambda x: x[0] tells bisect to compare only start times
  • bisect_right(events, e, key=lambda x: x[0]) finds the leftmost position where startTime > e
  • If such an event exists (idx < n), add the best value from that position (f[idx]) to the current event's value
  • Update the answer with the maximum value found

Time Complexity: O(n log n) where n is the number of events

• Sorting: O(n log n)
• Precomputation: O(n)
• For each event, binary search: O(log n), total O(n log n)

Space Complexity: O(n) for the precomputed array f

Example Walkthrough

Let's walk through the solution with a small example: events = [[1,3,4], [3,4,3], [5,6,5]]

Step 1: Sort the events by start time After sorting: [[1,3,4], [3,4,3], [5,6,5]] (already sorted in this case)

• Index 0: [1,3,4] - starts at 1, ends at 3, value = 4
• Index 1: [3,4,3] - starts at 3, ends at 4, value = 3
• Index 2: [5,6,5] - starts at 5, ends at 6, value = 5

Step 2: Build the precomputed array f We build f from right to left, where f[i] = maximum value from index i to the end:

• f[2] = 5 (only event at index 2, value = 5)
• f[1] = max(f[2], events[1][2]) = max(5, 3) = 5 (best from index 1 onwards is 5)
• f[0] = max(f[1], events[0][2]) = max(5, 4) = 5 (best from index 0 onwards is 5)

Result: f = [5, 5, 5]

Step 3: Process each event and find best combinations

Processing event [1,3,4] (index 0):

• End time = 3, value = 4
• Binary search: Find first event starting after time 3
  • bisect_right with key on start times finds index 2 (event [5,6,5] starts at 5 > 3)
• Total value = 4 + f[2] = 4 + 5 = 9
• Update answer: ans = max(0, 9) = 9

Processing event [3,4,3] (index 1):

• End time = 4, value = 3
• Binary search: Find first event starting after time 4
  • bisect_right finds index 2 (event [5,6,5] starts at 5 > 4)
• Total value = 3 + f[2] = 3 + 5 = 8
• Update answer: ans = max(9, 8) = 9

Processing event [5,6,5] (index 2):

• End time = 6, value = 5
• Binary search: Find first event starting after time 6
  • bisect_right finds index 3 (no events after, idx = 3 = n)
• Since idx >= n, no valid second event exists
• Total value = 5 (just this event)
• Update answer: ans = max(9, 5) = 9

Final Answer: 9

The maximum value is achieved by attending events [1,3,4] and [5,6,5], which don't overlap and give a total value of 4 + 5 = 9.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity is dominated by:

1. Sorting the events array: O(n × log n)
2. Building the suffix maximum array f: O(n) - single pass through the array
3. For each event in the main loop (n iterations):
   • bisect_right operation with custom key: O(log n) binary search
   • Other operations: O(1)
   Total for this loop: O(n × log n)

Overall time complexity: O(n × log n) + O(n) + O(n × log n) = O(n × log n)

Space Complexity: O(n)

The space complexity consists of:

1. The suffix maximum array f: O(n) - stores n elements
2. The sorting operation (Python's Timsort): O(n) in worst case
3. Other variables (ans, idx, loop variables): O(1)

Overall space complexity: O(n)

Where n is the number of events in the input array.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Overlap Definition

A critical pitfall is misunderstanding when two events overlap. Many developers incorrectly assume that if one event ends at time t and another starts at time t, they don't overlap. However, according to the problem, these events DO overlap - you need the next event to start at t + 1 or later.

Incorrect Implementation:

# WRONG: This would find events where start_time >= end_time
left, right = 0, n
while left < right:
    mid = (left + right) // 2
    if events[mid][0] >= end:  # Wrong comparison!
        right = mid
    else:
        left = mid + 1

Correct Implementation:

# CORRECT: Find events where start_time > end_time
left, right = 0, n
while left < right:
    mid = (left + right) // 2
    if events[mid][0] > end:  # Strict inequality
        right = mid
    else:
        left = mid + 1

2. Not Considering Single Event as Answer

Another pitfall is forgetting that attending just one high-value event might be better than attending two lower-value events. The precomputed array handles this, but if you try to optimize and only look for pairs, you'll miss cases where a single event has the maximum value.

Example: Events: [[1,2,10], [4,5,1], [6,7,1]]

• Best two events: value = 10 + 1 = 11
• But if we had [[1,2,20], [4,5,1], [6,7,1]], the single event with value 20 is better than any pair

Solution: The code correctly handles this by initializing current_sum = value (considering the single event) before potentially adding a second event.

3. Off-by-One Error in Precomputation

When building the max_value_from array, starting from the wrong index or using wrong boundaries can cause incorrect results.

Incorrect:

# WRONG: Missing the last event's value
max_value_from = [0] * n
for i in range(n - 2, -1, -1):
    max_value_from[i] = max(max_value_from[i + 1], events[i][2])

Correct:

# CORRECT: Initialize last element first
max_value_from = [0] * n
max_value_from[-1] = events[-1][2]  # Don't forget this!
for i in range(n - 2, -1, -1):
    max_value_from[i] = max(max_value_from[i + 1], events[i][2])

4. Using bisect_left Instead of Custom Binary Search

Using bisect_left or bisect_right without proper understanding can lead to wrong results. The problem requires finding the first event where start_time > end_time, which needs careful implementation.

Why the manual binary search is clearer:

• It explicitly shows we're looking for events[mid][0] > end
• The condition is unambiguous
• Using bisect_right(events, end, key=lambda x: x[0]) would find where to insert end to keep the list sorted by start times, which gives us the first event with start_time > end

5. Not Handling Edge Cases

Forgetting to check if a valid second event exists before accessing the precomputed array.

Incorrect:

# WRONG: May cause index out of bounds
current_sum = value + max_value_from[left]

Correct:

# CORRECT: Check bounds first
current_sum = value
if left < n:
    current_sum += max_value_from[left]