Coding Patterns: Merge Intervals

1. Brute Force Approach

A simple approach is to start from the first interval and compare it with all other intervals for overlapping, if it overlaps with any other interval, then remove the other interval from the list and merge the other into the first interval. Repeat the same steps for the remaining intervals after the first. 

Time Complexity: O(n²)                                             

Space Complexity: O(n)                                                                      

2. Merge Overlapping Intervals                                       

The idea to solve this problem is, first sort the intervals according to the starting time. Once we have the sorted intervals, we can combine all intervals in a linear traversal. The idea is, in sorted array of intervals, if interval[i] doesn’t overlap with interval[i-1], then interval[i+1] cannot overlap with interval[i-1] because starting time of interval[i+1] must be greater than or equal to interval[i].

 

Problem: Merge Intervals

LeetCode 56 - Merge Intervals [medium]                                                                 

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.

class Solution:                                                                              
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:            
        if len(intervals) == 0:                                                              
            return []                                                                               
        intervals = sorted(intervals, key = lambda x: x[0])                   
        result = [intervals[0]]                                                                 
        for interval in intervals[1:]:                                                        
            if interval[0] <= result[-1][1]:                                                  
                result[-1][1] = max(interval[1], result[-1][1])                     
            else:                                                                                   
                result.append(interval)                                                   
        return result                                                                            

Time complexity: O(N*log(N))
Auxiliary Space: O(N)

We iterate the list once so the total cost will be O(N log N) because the sort function in python is O(N log N).

2.Solution:                                                                                

 

Follow the steps mentioned below to implement the approach:

• Sort all intervals in increasing order of start time.
• Traverse sorted intervals starting from the first interval, 
• Do the following for every interval.
  • If the current interval is not the first interval and it overlaps with the previous interval,
     then merge it with the previous interval. Keep doing it while the interval overlaps with the previous one.         
  •  Otherwise, Add the current interval to the output list of intervals.
  •  

class Solution:                                                                              
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:            
        def overlap(a, b):                                                                    
            if a[1] >= b[0] and b[1] >= a[0]:                                            
                return True                                                                      
            else:                                                                                  
                return False                                                                
        i = 0                                                                                       
        intervals=sorted(intervals)                                                     
        while i < (len(intervals) - 1):                                                          
            if overlap(intervals[i],intervals[i + 1]):                                        
                intervals[i]=[min(intervals[i][0],intervals[i + 1][0]),max(intervals[i][1],intervals[i + 1][1])]
                intervals.remove(intervals[i + 1])                                                                       
            else:                                                                                                       
                i += 1                                                                                
        return intervals                                                            

Time Complexity: O(N * log N) where N is the total number of intervals. In the beginning, since we sort the intervals, our algorithm will take O(N * log N) to run.

This approach is quite useful when dealing with intervals, overlapping items, or merging intervals.