Leetcode 56. Merge Intervals

By / March 14, 2022

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Leetcode 56. Merge Intervals

One of the medium-hard problems found on Leet Code is known as “Merge Intervals.” This challenge gives us a list of lists of the start and end values of an interval, and we have to check to see if there are any overlapping intervals. If yes, then we are to merge those intervals into one. 

Although there are multiple approaches to solve this challenge, you will be finding the best two below. Keep reading this post to find the solution to the “Merge Intervals” Leet Code challenge.

Method 1

The first method to merge the overlapping intervals from a given list of lists is to think of the problem as a number line. Think of drawing the intervals on the number line, and you might visualize that some of them will overlap if there are some. 

To solve this problem, we follow a series of simple steps. 

For clarification, we shall use:

    numList: The input list of lists containing the intervals
    resList: The output list which will be returned with the merged intervals
       

Now, firstly we shall sort the numList in ascending order. We can easily do so by using the built-in sort() method with the key as the first element of the sub-lists of numList. 

After sorting the numList, we now need to assign the first sub-list of numList to the variable resList for cross-referencing our overlapping sequence with the second element of numList. Now that we’ve made the assignment, it is time to start the overlapping check sequence. 

To check for the overlapping, you create a general loop with two variables, ‘start’ and ‘end,’ to iterate through the numList from the second element to the last. We start from the second element because we have already stored the first sub-list in ‘resList.’

Next, we assign to the endElem the last element of the previous sub-list stored in resList. We do this to compare if our next sub-list overlaps the previous or not. 

To do so, we will use an IF-ELSE conditional statement. IF endElem is less than or equal to the ‘start,’ we will use the built-in max() function to attain the maximum of endElem and ‘end’ and assign it to the last element of the previous sub-list of resList. IF the condition is not met, append a list containing ‘start’ and ‘end’ to the list resList.

Finally, we return the resList. 

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        
        intervals.sort(key=lambda x: x[0])
        resList = [intervals[0])]

        for (start, end) in intervals[1:]:
            if resList[-1][1] >= start and end > resList[-1][1]:
                resList[-1][1] = end
            elif resList[-1][1] < start:
                resList.append([start,end])

        return resList

And this is it. You are done. You have successfully merged the overlapping intervals with O(log n) time complexity. 

Method 2

The second method to merge overlapping intervals is somewhat, as we like to call it, “brute-testing.” This means that for each element, we linearly search the entire data structure/s to compute a result and continue to do so for every element in the data structure. 

First, we need to sort the sub-lists in our input list. We will use the built-in sort() method, and the key would be the first element of the sub-lists.

To carry on with this method, we first create a ‘variable’ and a list called ‘resList,’ which will be our output list.

To start off, we will assign the first element of our input list to the temp variable. We will iterate through the input list with our pointer at the 0th position. We will compare the 0th value of our pointer’s list from the input list and the 0th value of our list in temp. If the value at the pointer is greater than equal to the 0th element and less than or equal to the 1st element of the temp list, then it means it is overlapping.

In this case, we will replace the list in temp variable as follows:

    0th element = lowest number from  the 0th element of temp list and pointer’s list
    1st element = maximum number from the 1st element of temp list and pointer’s list

If the condition is not met, then the current list stored in the temp will be appended to the resList. However, after both cases, the pointer will be incremented to the second position, and the same process will be repeated.

In the end, when the input list is exhausted by the pointer, the resList will be returned. If you followed the steps correctly, your problem would be executed successfully in the time complexity equal to O(log n).

def merge(self, intervals: List[List[int]]) -> List[List[int]]:

    intervals.sort(key=lambda x: x[0])

    result = []
    prestart = intervals[0][0]
    preend = intervals[0][1]

    for i in range(1,len(intervals)):
        start = intervals[i][0]
        end = intervals[i][1]
        if preend >= start and prestart <= end:
            prestart = min(prestart,start)
            preend = max(preend, end)
        else:
            result.append([prestart,preend])
            prestart = start
            preend = end
    result.append([prestart,preend])
    return result

Related Posts

Scroll to Top