Two Best Non Overlapping Events - Leetcode Solution

The Two Best Non Overlapping Events problem on LeetCode is a problem in which we are given a list of events with their start and end times. We need to find two events that do not overlap and have the maximum total duration.

To solve this problem, we can follow the below steps:

1. First, we need to sort the events based on their end times. This is because we want to find the event which ends first and then the event which ends second. Sorting on end times will make this easier.

2. Next, we can iterate through the events and keep track of the events that do not overlap. We can use two pointers, i and j, to keep track of the events. Initially, i and j will point to the first event in the list and we will set the maximum duration to zero.

3. We can then compare the end time of event i with the start time of event j. If the end time of event i is less than or equal to the start time of event j, then these events do not overlap. We can calculate the duration of these two events and check if the sum of their duration is greater than the current maximum duration. If it is, we update the maximum duration.

4. If the events do overlap, we need to move the pointer j to the next event. We can do this by incrementing j.

5. We can continue the above steps until we reach the end of the list of events. Once we have gone through all the events, we will have the two best non-overlapping events with the maximum duration.

Below is the code implementation and time complexity analysis of the solution:

def maxEvents(events):
    events.sort(key=lambda x: x[1]) # sorting based on end times
    i, j = 0, 1 # two pointers
    max_duration = 0 # maximum duration

    while j < len(events): # continue until the end of the list
        if events[i][1] <= events[j][0]: # not overlapping
            duration = events[i][1] - events[i][0] + events[j][1] - events[j][0] # calculate duration
            max_duration = max(max_duration, duration) # update maximum duration
            i += 1 # move the pointer i
        j += 1 # move the pointer j

    return max_duration

The time complexity of this solution is O(nlogn), where n is the number of events. This is because we are sorting the events based on end times, which takes O(nlogn) time. The rest of the algorithm takes O(n) time. Thus, the overall time complexity is O(nlogn).

1