In this post, we’ll discuss the Merge Intervals problem from Leetcode.
Table of Contents
The Merge Intervals Problem
For this challenge, your task is to write a function called merge() that accepts an argument called intervals.
intervals is a 2 dimensional list, with each nested list representing an interval.
The function merges all overlapping intervals in intervals and returns the merged intervals.
Let’s look at some examples.
Example 1
Suppose
intervals = [[1,3],[2,6],[8,10],[15,19], [16, 18]]
The nested lists in intervals can be represented as the following intervals:
As you can see from the image above, the green ([2, 6]) and orange ([1, 3]) intervals overlap each other. Hence, the merge() function should merge these two intervals into a single interval [1, 6].
Similarly, the purple ([16, 18]) and blue ([15, 19]) intervals also overlap each other. Hence, the merge() function should merge these two intervals into the interval [15, 19].
As a result, the function should return the list [[1, 6], [8, 10], [15, 19]].
Example 2
Next, let’s look at another example. Suppose
intervals = [[1,4],[4,5], [7, 9], [7, 9]]
For the Leetcode Merge Intervals problem, intervals that are adjacent to each other (with no gap in between) are considered to be overlapping. Hence, in the example above, [1, 4] and [4, 5] are overlapping.
In addition, duplicate intervals are also considered to be overlapping. Hence, [7, 9] and [7, 9] are overlapping.
As a result, the merge() function should return the list [[1, 5], [7, 9]].
Suggested Approach
Step 1: Sort the input list
To solve the Merge Intervals problem, the easiest way is to sort intervals based on the start of each interval (i.e. based on the first element in each nested list).
For instance, if intervals = [[8, 9], [2, 3], [7, 10], [1, 4]], we’ll sort it as
intervals = [[1, 4], [2, 3], [7, 10], [8, 9]]
[1, 4] comes before [2, 3] as 1 is smaller than 2. Similarly, [7, 10] comes before [8, 9] as 7 is smaller than 8.
When intervals is not sorted, if we want to determine if an interval (say [2, 3]) overlaps with another interval, we need to check all the nested lists in intervals.
In contrast, when it is sorted, to check if [2, 3] overlaps with another interval, we only need to check the interval before it (i.e. we only need to check [1, 4]).
In addition, sorting by the start of each interval ensures that when two intervals overlap each other, the merged interval starts from the start of the first interval.
For instance, consider the intervals [7, 10] and [8, 9].
[7, 10] comes before [8, 9] as 7 is smaller than 8. When we merge these two intervals, the merged interval ([7, 10]) starts from 7, which is the start of the first interval.
Step 2: Declare a New List to Store the Merged Intervals
After sorting intervals, we need to declare a new list to store the merged intervals. Let’s call this list result. We’ll add the first element in intervals to result.
Step 3: Iterate through intervals
Next, we need to iterate through intervals, starting from the second interval (i.e. the second element). For each interval in intervals, we check if it starts after the last interval in result.
For instance, if
result = [[1, 5], [6, 9]]
we check if the current interval in intervals starts after 9.
Case 1: When an overlap is found
Suppose the current interval is [7, 12].
As 7 is smaller than 9, we know that [7, 12] overlaps with [6, 9]. Hence, we need to merge the two intervals.
To do that, we only need to update the last interval in result (i.e. [6, 9]), by changing the end of that interval.
The end of the merged interval is the greater among the ends of [6, 9] and [7, 12]. Hence, we update the last interval in result to [6, 12].
Case 2: When an overlap is not found
On the other hand, if the start of the current interval is greater than the end of last interval in result, we know that the two intervals do not overlap.
For instance, suppose the current interval is [11, 14].
As 11 is greater than 9, [11, 14] does not overlap [6, 9].
Hence, we do not need to modify [6, 9]. Instead, we add [11, 14] to result.
Step 4: Return result
After iterating through all the elements in intervals, result stores the merged intervals. We simply need to return result and the function is complete.
Graphical Illustration
Here’s a graphical illustration of how the approach above works for the Merge Intervals problem:
Suggested Solution
Here’s the suggested solution for the Merge Intervals problem in Python:
def merge(intervals):
if len(intervals) == 0 or len(intervals) == 1:
return intervals
intervals.sort(key=lambda x:x[0])
result = [intervals[0]]
for interval in intervals[1:]:
if interval[0] <= result[-1][1]:
result[-1][1] = max(result[-1][1], interval[1])
else:
result.append(interval)
return resultHere, we first define a function called merge() with one parameter intervals.
Inside the function, we check if intervals is empty or has one element. If any of the above is true, we do not need to do any merging as the answer is simply intervals itself. Hence, we return intervals on line 4.
On the other hand, if intervals has more than one element, we proceed to line 6.
Sorting intervals
Here, we use the pre-defined sort() function to sort intervals. If you are unfamiliar with the sort() function, you can check out this post where we discuss how to use the sort() function with the key argument.
Simply stated, the key argument allows us to specify how we want to sort our list. In our code above, we assign the following lambda function
lambda x:x[0]
to it.
This lambda function accepts an argument x and returns the value of x[0]. In other words, x is a list and the function returns the first element in x. This allows us to sort intervals based on the first element in each nested list.
For instance, if intervals equals [[6, 10], [11, 15], [2, 5], [1, 4], [7, 9]], it becomes [[1, 4], [2, 5], [6, 10], [7, 9], [11, 15]] after sorting.
Initializing result
Next, we proceed to line 7 where we initialize a list called result.
result is a 2 dimensional list that contains one element at the moment – the first interval in intervals.
Iterating through intervals
After initializing result, we proceed to the for loop (from lines 9 to 13).
This loop iterates through intervals, starting from the second element in intervals.
For each element (interval) in intervals, we check if interval[0] is smaller than or equal to result[-1][1].
For instance, if
intervals = [[1, 4], [2, 5], [6, 10], [7, 9], [11, 15]]
The first time the loop runs,
result = [[1, 4]] interval = [2, 5] interval[0] = 2 result[-1] = [1, 4] # The last element in the 2D list result result[-1][1] = 4
As 2 <= 4 is true, the if block is executed and result[-1][1] is updated to the greater value between result[-1][1] and interval[1] (i.e. between 4 and 5).
As a result, result is updated to [[1, 5]].
On the other hand, if interval[0] is not smaller than or equal to result[-1][1], the else block is executed. In our example above, this happens the second time the loop runs:
result = [[1, 5]] interval = [6, 10] interval[0] = 6 result[-1] = [1, 5] # The last element in the 2D list result result[-1][1] = 5
As 6 <= 5 is not true, the else block is executed. Inside the else block, we append the new interval [6, 10] to result.
result becomes [[1, 5], [6, 10]].
We keep iterating through intervals and comparing each interval with the last element in result, until we finish all the elements in intervals.
When that happens, result stores the merged intervals and we return its value on line 15.
With that, the function is complete.