Merge Intervals — Day 24(Python)

Photo by pine watt on Unsplash

Todays’ question is on the topic Array and Sorting. It is one of the favorite problems among FANG interviewers.

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.

  1. Sort the array.

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.

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store