The task of calendar gaps merging
Let’s suppose you are working in a company and it is developing an electronic calendar. The calendar has a function that shows when various programming teams will be busy at a meeting.
Those periods when the team is busy are marked on the calendar as time ranges, for example, from 10:00 to 12:30 or from 12:30 to 13:00. In the developed program, the time interval is presented in the form of tuples of two integers. The number indicates the number of the 30-minute block, which comes after 9:00 am. For example, a tuple (2, 4) means a range from 10:00 to 11:00, and (0, 1) is a span of 9: 00-9: 30.
You need to write a function that should simplify the output of information in such a way that if the team is busy from 10:00 to 12:30 and from 12:30 to 13:00, then it was displayed as 10: 00‒13: 00. For example: the input of your function is an unordered array of tuples [(0, 1), (3, 5), (4, 8), (10, 12), (9, 10)], and you must get an ordered array at the output [(0, 1), (3, 8), (9, 12)].
In the future, it is planned to make changes to the program, where instead of the 30-minute blocks there will be minute minutes, as implemented in the Unix-time view. Given this change, you need your function to be able to work with large numbers right now. Do not forget that a tuple is a data type in which the contents of a variable cannot be changed after its creation.
Actually, you can come up with a lot of solutions, but you are required to provide the most efficient and optimized code. First, you need to sort the array, so it will be more convenient to combine nearby time ranges since they will be one after another. Then we will go through our array from left to right and at each step, we will perform one of two options:
Merge the current range with the previous one, saving the result in case another merge is required.
Store the saved result in the output array merged_meetings, provided that the current range is not combined with the previous one, like all subsequent ones.
It is also necessary to ensure that the last saved result is saved the output array since there will not be the same condition as with the previous ones: the absence of the next range that will not merge with the current one.
Python solution code:
def merge_ranges(meetings): # sort the input array by putting it in sorted_meetings. sorted_meetings = sorted (meetings) # create an output array that is empty so far. merged_meetings =  previous_meeting_start, previous_meeting_end = sorted_meetings  for current_meeting_start, current_meeting_end in sorted_meetings [1:]: # If the current range can be combined with the previous one. if current_meeting_start <= previous_meeting_end: # Save the result in case # current range will be expanded again. previous_meeting_end = max (current_meeting_end, previous_meeting_end) # If the current range cannot be combined with the previous one. else: # insert the result into the output array merged_meetings.append ((previous_meeting_start, previous_meeting_end)) previous_meeting_start, previous_meeting_end = \ current_meeting_start, current_meeting_end # insert the last result. merged_meetings.append ((previous_meeting_start, previous_meeting_end)) return merged_meetings
The algorithm’s complexity is O(n lg n) by time and O(n) by memory. O(n lg n) appeared due to the fact we have sorted the array before passing through it.