Merge Overlapping Events In The Same Hall - Leetcode Solution

Problem statement: You are given a list of events where each event has a start time and an end time. Events in the same hall are overlapping, you need to merge all the events happening in the same hall.

Input: You are given an array of tuples where each tuple contains the following elements:

1. Hall Number
2. Starting Time
3. Ending Time

Output: You need to return an array of tuples where each tuple contains the following elements:

1. Hall Number
2. Starting Time
3. Ending Time

where all the overlapping events belonging to the same hall have been merged.

Approach: The problem can be solved using a greedy approach. We will sort the events first by start time and then by hall number. We will then iterate over the events and merge the overlapping events belonging to the same hall.

Algorithm:

1. Sort the given array of events by start time and then by hall number
2. Initialize an empty list of result events
3. For each event e in the sorted list, if the result list is empty, add e to the list
4. Otherwise, if the hall number of e is same as the last event in result list, merge e with the last event and update the end time of the last event in the result list
5. If the hall number of e is different from the last event in the result list, add e to the result list
6. Return the result list

Time Complexity: The time complexity of the algorithm is O(nlogn) where n is the number of events.

Space Complexity: The space complexity of the algorithm is O(n) where n is the number of events.

Code:

def merge_events(events):
    #sort events by start time and then by hall number
    events.sort(key = lambda e: (e[1], e[0])) 
    result = []
    #iterate over events and merge if required
    for event in events:
        if len(result) == 0:
            result.append(event)
        elif event[0] == result[-1][0] and event[1] <= result[-1][2]:
            result[-1] = (event[0], result[-1][1], max(result[-1][2], event[2]))
        else:
            result.append(event)
    return result

#test case:
events = [(1, 1, 3), (1, 2, 4), (2, 5, 6), (3, 4, 7), (3, 2, 4), (2, 1, 5)]
print(merge_events(events))

#Output: [(1, 1, 4), (2, 1, 6), (3, 2, 7)]

Explanation: In the given example, the sorted events are:

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

We start with the first element: (1, 1, 3) and add it to the result because the result is empty.

We then move on to the second element: (1, 2, 4). Since it has the same hall number as the last event in the result list and its start time is less than or equal to the end time of the last event in the result list, we merge the two events and update the end time of the last event in the result list to 4.

Next, we move on to the third element: (2, 1, 5). Since it has a different hall number than the last event in the result list, we simply add it to the list.

Then we move on to the fourth element: (2, 5, 6). Since it has the same hall number as the last event in the result list and its start time is greater than the end time of the last event in the result list, we add it to the result list.

Next, we move on to the fifth element: (3, 2, 4). Since it has a different hall number than the last event in the result list, we add it to the list.

Finally, we move on to the sixth element: (3, 4, 7). Since it has the same hall number as the last event in the result list and its start time is greater than the end time of the last event in the result list, we merge it with the last event in the result list and update the end time of the last event in the result list to 7.

Thus, the final result is [(1, 1, 4), (2, 1, 6), (3, 2, 7)]

1