🤝56. Merge Intervals

Medium | Grind 75 | Thursday August 4, 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.

Constraints:

• 1 <= intervals.length <= 104

• intervals[i].length == 2

• 0 <= starti <= endi <= 104

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] overlap, 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.

SOLUTION

The question is straightforward, but, we need to pay close attention to the constraints. The two values inside each element will always be non-decreasing. However, the intervals/elements themselves do not strictly have to be non-decreasing. Given this, we will first sort the intervals. By using python's built-in sort function, it will sort the intervals based on their first start value. For example, if the input is [[1,3],[2,6],[8,10],[5, 18]], the sorted list would be [[1,3],[2,6],[5,18],[8,10]]

Once we have the sorted intervals, we will loop through each element in the intervals list. We know that an overlap exists when the end (second value in an element) value is greater than or equal to the start value of the next element. In example 1, our first element is [1,3]. The start is 1 and the end is 3. We now compare our end with the start of the next element which is 2. Since 3 is bigger than 2, we know there is an overlap. We can now merge these two intervals. NOTE: whenever you merge, you need to be careful of the end values because the end value of the next element may not necessarily be greater than the end value of the current element.

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort() # will sort it based on the first value of each element
        output = []      # store our merged intervals here. 
        i= 0  
        
        while i < len(intervals):  
            start, end = intervals[i][0], intervals[i][1] # get the start and end of an element.
            
            # need to loop only unitl len - 2 to not get index error since we add i+1 
            while i <= len(intervals)-2:
                # keep iterating if the current end is more than the start of the next element.
                # if end > start of next element, means an overlap exist. 
                if end >= intervals[i+1][0]:
                    
                     # need to update the end. the end value for the next element could be smaller than the current end. 
                    if end < intervals[i+1][1]:
                        end = intervals[i+1][1]
                        
                    # go to the next element and repeat
                    i += 1
                    
                else: 
                    break
            
            # this will be the merged interval. 
            output.append([start, end])
            i += 1
        
        return output

TIME AND SPACE COMPLEXITY

TIME: we are looping through all the elements once so the time for this will be O(n) where n is the number of elements in the interval list. However, Given that we are sorting, the time complexity for that is O(nlogn). Therefore, our time complexity is O(nlogn).

SPACE: space complexity will be O(n). In the worst-case scenario, none of the elements overlap so we have to store every element in our output list.