56. Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].Example 2:
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.Let us try to understand the question better. We have a list of lists that contain a start time and an end time. End time will always be larger than the start time. We need to merge lists that have overlapping intervals, which means if we have two lists and the start time of the second list is lesser than the end time of the first list, then we merge both and form a new list with a start time as lesser start time among both list and end time as higher among both the end time.
Wouldn’t it be easier for us to solve this problem if we could sort the list? By sorting, we can get earlier start times and merge the interval is required.
In python, we can make use of lambda to sort a list of lists. We need to ensure that the start times are sorted, in ascending order, and in case of a tie, the list with a bigger end time will come first.
sorted_list = sorted(intervals, key = lambda x :(x[0],-x[1]))
After sorting, we will compare the start time and end time.
- Sort the array.
- Initialize an empty output array.
- Pop the first list from the sorted array and save it in the output array.
- From the next list, compare the latest end time with the new lists start time. If the start time is lesser than the end time, merge them or else, consider the new list as a new interval. In the case of merging the end time will always be higher among both the comparing end times.
The code will look like below.
class Merger:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
if len(intervals) == 0:
return []
sorted_list = sorted(intervals, key = lambda x :(x[0],-x[1]))
output = []
output.append(sorted_list.pop(0))
while(sorted_list):
if output[-1][-1] >= sorted_list[0][0]:
output[-1][-1] = max(output[-1][-1], sorted_list[0][1])
sorted_list.pop(0)
else:
output.append(sorted_list.pop(0))
return(output)Complexity analysis
Time Complexity
We are sorting our list using python in-built sorting function. The time complexity of sorting is O(NlogN). We are traversing through the entire list once after sorting, which takes O(N). Since O(NlogN) is higher than O(N) where N is the number of lists.
Space Complexity
We are not using any extra space while finding the solution, except for the output array. We do not consider space used for output array, and hence space complexity is O(1).
I would love to hear your feedback about my posts. Do let me know if you have any comments or feedback.
