Two Best Non-Overlapping Events

main.md

Question

Approach

I sort the events by their start time. As I iterate through events in increasing start order, I want to know the maximum value of any event that has already ended before the current event starts.

To do this efficiently:

• I keep another list of events sorted by end time.
• I maintain a pointer over the end-sorted list and a running maximum best_so_far of values for all events whose end < current_start.
• For each event, I compute:
  • taking only this event
  • taking this event + the best non-overlapping previous event

I update the answer with the maximum of these options. This guarantees I always combine an event with the best compatible earlier event.

Implementation

class Solution:
    def maxTwoEvents(self, events: List[List[int]]) -> int:
        events.sort(key=lambda x: x[0])
        
        end_sorted = sorted(events, key=lambda x: x[1])
        
        ans = 0
        best_so_far = 0
        j = 0 
        
        for start, end, value in events:
            while j < len(end_sorted) and end_sorted[j][1] < start:
                best_so_far = max(best_so_far, end_sorted[j][2])
                j += 1
            
            ans = max(ans, value + best_so_far)
        
        return ans

Complexities

• Time: O(n logn)
• Space: O(n)

    for start, end, value in events: