2054. Two Best Non-Overlapping Events

Problem Description

You are provided with a list of events, each represented by a trio of integers: the start time, the end time, and the event's value. The goal is to maximize the total value by attending up to two non-overlapping events. It's important to note that if two events share a start or end time, they are considered overlapping and thus cannot both be attended; to attend consecutive events, the next event must start after the previous event has ended.

Intuition

To tackle this problem, think of it as two separate scenarios: either you attend only one event or you attend two non-overlapping events.

For any given event, the best strategy is to attend the event itself and then add it to the value of the next non-overlapping event (if any) that yields the maximum value. To simplify this process, the events are sorted by their start time, which allows for efficient searching of the next non-overlapping event using binary search.

To streamline the search for the maximum value of a non-overlapping event that starts after a given end time, you precalculate and store the outcome in an array f, avoiding the need to compute it multiple times. This array holds the maximum event value from the current event to the last event. By updating this array from the end towards the start, you ensure that f[i] represents the maximum event value from event i to the end. This approach enables you to easily find the maximum value that can be added to the current event value.

When considering a particular event, you find the next non-overlapping event by conducting a binary search to locate the index of the first event that starts after the current event's end time. Using binary search is efficient here due to the events being sorted. Once this index is obtained, you can add the value of the current event with the value stored at this index in your precalculated f array to get the total value if you were to attend both events.

Finally, you compare the value obtained by attending the current event and possibly the next non-overlapping event to the previously calculated maximum sum and continually update this maximum. This iterative approach ensures that by the time you finish examining all events, you have determined the maximum total value that can be achieved by attending up to two non-overlapping events.

The solution capitalizes on sorted event start times and binary search for efficiency, combined with dynamic programming to precalculate possible future values, ensuring an optimized and speedy result.

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

Solution Approach

The solution is built around a smart combination of sorting, binary search, dynamic programming, and greedy approach.

1. Sorting: First, we sort the events by their start time. This step is crucial for the binary search that follows and ensures that when we look for the next non-overlapping event, we can do so efficiently.

2. Dynamic Programming: We prepare an array f which will, at each position i, store the maximum value of an event that starts from i until the end of the array. This array represents the best future event value we can get if we decide to attend an event starting from any position i. To populate this array, we iterate from the end of the list backward, constantly keeping track of the highest value seen so far.

   1f = [events[-1][2]] * n
   2for i in range(n - 2, -1, -1):
   3    f[i] = max(f[i + 1], events[i][2])

3. Greedy Approach: For each event, we consider the maximum sum we can get by attending the current event and then look ahead to find the next possible non-overlapping event that we could attend. We use a greedy approach to always pick the next best choice without considering the broader problem.

   1ans = 0
   2for _, e, v in events:
   3    idx = bisect_right(events, e, key=lambda x: x[0])
   4    if idx < n:
   5        v += f[idx]
   6    ans = max(ans, v)

4. Binary Search: For finding the index of the first event that starts after the current event ends, we use the bisect_right function. This standard library function implements a binary search algorithm that returns the index of the first element in the events that is greater than the e, which is the ending time of the current event:

   1idx = bisect_right(events, e, key=lambda x: x[0])

5. Final Calculation and Iteration: As we iterate over each event, for the current event, we set v to be its value, then we add to v the value stored in f at the idx position found using binary search if it's within bounds. This total value of v now represents the maximum sum obtained by attending the current event and the best possible next non-overlapping event. We update the maximum answer we have seen so far:

   1if idx < n:
   2    v += f[idx]
   3ans = max(ans, v)

By the end of the loop, ans will hold the maximum possible sum of the values of at most two non-overlapping events.

Example Walkthrough

Let's illustrate the solution with a small example. Suppose we have the following events, where each event is a trio of integers (start time, end time, value):

1events = [(1, 3, 5), (2, 5, 6), (4, 6, 5), (7, 8, 4)]

1. Sorting: We sort the events by their start time. However, the events are already sorted in this example, so we don’t need to sort them again.

2. Dynamic Programming: We initialize the f array to prepare for maximum future event values. Since we have 4 events, our array will have 4 positions:

   1n = len(events)  # n is 4
   2f = [0] * n

   Now we populate f from right to left, keeping track of the highest value:

   1f = [5, 5, 5, 4]  # Initialized with the last event's value
   2f[2] = max(f[3], events[2][2])  # f[2] is max(4, 5)
   3f[1] = max(f[2], events[1][2])  # f[1] is max(5, 6)
   4f[0] = max(f[1], events[0][2])  # f[0] is max(6, 5)

   After iteration, f becomes [6, 6, 5, 4].

3. Greedy Approach: We now iterate through events and use a greedy approach to sum values of the current event and the next non-overlapping event:

   1ans = 0
   2idx = bisect_right(events, 3, key=lambda x: x[0])  # idx for event (1, 3, 5)
   3if idx < n:
   4    v = events[0][2] + f[idx] # v = 5 (current value) + 6 (next non-overlap)
   5    ans = max(ans, v) # ans is max(0, 11)
   6
   7idx = bisect_right(events, 5, key=lambda x: x[0])  # idx for event (2, 5, 6)
   8# The rest of the events start after event (2, 5, 6) ends.

   And so on for the remaining events. We continue updating ans with the maximum values obtained.

4. Binary Search: We use bisect_right to efficiently find the non-overlapping event:

   1idx = bisect_right(events, e, key=lambda x: x[0])

5. Final Calculation and Iteration: We update v with the sum of the current event's value and the max future value if the index is within bounds. Then update ans:

   1if idx < n:
   2    v = events[i][2] + f[idx]
   3ans = max(ans, v)

After finishing the loop, ans will be the maximum sum of values that can be achieved by attending up to two non-overlapping events. For this example, ans would be the maximum value obtained, demonstrating which events to choose to maximize the value.

Solution Implementation

Time and Space Complexity

The given code is designed to find the maximum value that can be obtained by attending at most two events, where events is a list of event intervals, each in the format [start, end, value]. Here's the analysis of its time and space complexity:

Time Complexity

1. Sorting events: The initial sorting of the event list events.sort() has a time complexity of O(n log n), where n is the number of events.

2. Backward traversal to fill f: The loop that fills the list f with the maximum value of the events that come after each event has a time complexity of O(n) as it goes through the list of events once.

3. Binary search using bisect_right: In the worst case, the binary search is called for each event to find the index idx. Since bisect_right has a complexity of O(log n), and it's called inside a loop that runs n times, the total time complexity for this part is O(n log n).

4. Summing up the time complexities from the above points, we have O(n log n) + O(n) + O(n log n), which simplifies to O(n log n) since the log n terms dominate the linear term.

Space Complexity

1. Auxiliary list f: The space complexity is O(n) because of the additional list f, which has the same length as the list of events.

2. Constant space: No other significant space-consuming structures are used, so we only consider the space for f.

In conclusion, the total time complexity of the code is O(n log n) and the total space complexity is O(n).

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