2054. Two Best Non-Overlapping Events - Detailed Explanation

1. Problem Statement

Description:
You are given an array events where each event is represented as [startTime, endTime, value]. You want to attend at most two non-overlapping events such that the sum of their values is maximized. Two events are non-overlapping if the end time of the first event is strictly less than the start time of the second event. If no pair of non-overlapping events exists that gives a sum larger than taking one event alone, return the maximum value of a single event.

Examples:

1. Example 1:

   • Input: events = [[1, 3, 2], [4, 5, 2], [2, 4, 3]]
   • Output: 4
   • Explanation:
     You can attend the first event [1, 3, 2] and the second event [4, 5, 2] (since 3 < 4). Their total value is 2 + 2 = 4.

2. Example 2:

   • Input: events = [[1, 3, 2], [4, 5, 2], [1, 5, 5]]
   • Output: 5
   • Explanation:
     Although you could attend two events in some cases, here the single event [1, 5, 5] has a higher value than any valid pair (since it overlaps with the other events).

3. Example 3:

   • Input: events = [[1, 5, 3], [1, 3, 5], [4, 6, 1]]
   • Output: 5
   • Explanation:
     The best option is to take the event [1, 3, 5] (value 5) since pairing it with any other event does not increase the sum without overlap.

Constraints:

• The number of events can be large (e.g., up to 10⁵).
• Each event is represented as a triplet: [startTime, endTime, value] where
  • (1 \leq \text{startTime} \leq \text{endTime} \leq 10^9)
  • (1 \leq \text{value} \leq 10^6)

2. Hints

• Hint 1:
  Try sorting the events by one of the time parameters (for example, by start time). This will allow you to efficiently search for a candidate second event for each first event.

• Hint 2:
  Consider using binary search to quickly find, for any given event, the next event that starts after the current event’s end time. This can help you determine valid pairs.

Approaches

Approach 1: Sorting with Binary Search

Explanation

1. Sort the Events:
   First, sort the events by their start time. Sorting makes it easier to find a candidate second event that does not overlap with the current event.

2. Iterate and Binary Search:
   For each event (say, event i), use binary search to find the smallest index j such that events[j][0] (the start time) is greater than events[i][1] (the end time). This ensures that event j does not overlap with event i.

3. Calculate Sum:
   For each valid pair (i, j), calculate the total value by summing events[i][2] and events[j][2] and update the maximum sum accordingly.

4. Consider Single Event Case:
   It is also important to compare your pair sum with the maximum value from any single event because sometimes attending one event is optimal.

Pseudocode

sort events by start time

maxSum = 0
for i from 0 to events.length-1:
    firstValue = events[i][2]
    index = binarySearch(events, events[i][1] + 1)
    if index is found:
         candidate = firstValue + events[index][2]
         maxSum = max(maxSum, candidate)
    maxSum = max(maxSum, firstValue)  // in case a single event is optimal

return maxSum

Note: The binary search should find the first event whose start time is greater than the current event's end time.

Visual Walkthrough (for a simplified example)

Consider events:

events = [
  [1, 3, 2],
  [4, 5, 2],
  [2, 4, 3]
]

• After sorting by start time:

  [ [1, 3, 2], [2, 4, 3], [4, 5, 2] ]
  

• For event [1, 3, 2]:
  • Use binary search to find the first event with start > 3.
  • Found [4, 5, 2].
  • Sum = 2 + 2 = 4.
• For event [2, 4, 3]:
  • Search for event with start > 4.
  • Found [4, 5, 2] if condition is strict (if start must be greater than end, then 4 is not valid if we require > 4); adjust condition accordingly.
• For event [4, 5, 2]:
  • No valid event found, so consider its value alone.

Approach 2: Two-Pointer / Prefix Maximum Method

Explanation

1. Sort by End Time:
   Sort the events by their end time.

2. Build a Prefix Maximum Array:
   Create an array where each position stores the maximum event value seen so far (or the best candidate event’s value) up to that point. This helps you quickly retrieve the best possible event that ends before a given start time.

3. Binary Search for Non-Overlapping Event:
   For each event in the sorted-by-start order, use binary search on the sorted-by-end array to find the last event that ends before the current event’s start time. Use the prefix maximum array to get the best value from those events.

4. Combine Values:
   For each event, combine its value with the best candidate from before, and update the global maximum sum.

Comparison of Approaches

• Binary Search Approach (Approach 1) is straightforward when sorting by start time and directly pairing events.
• Prefix Maximum Approach (Approach 2) can be more efficient if you want to quickly access the best value among all events ending before a certain time.

Both methods have an overall time complexity of O(n log n) due to sorting and binary search operations.

Code Examples

Python Code