[Top Interview 150] 56. Merge Intervals

Solution)

 

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # Initialization
        intervals.sort()
        res = [intervals[0]]

        for start, end in intervals[1:]:
            lastEnd = res[-1][1]

            # If the current interval overlaps the previous interval
            if start <= lastEnd:
                res[-1][1] = max(lastEnd, end)
            else:
                res.append([start, end])
        
        return res

 
 
Problem: LeetCode
Reference: NeetCode
 
Time Complexity: O(n logn)
Space Complexity: O(n)
 
 

Explanation)
 

We'll first sort the intervals so that we can easily figure if the current interval overlaps the previous interval. We check the previous intervals by saving them in extra space.
 
We determine if intervals do overlap by checking if the current interval's start is smaller than or equal to the previous interval's end.
 
 

Initialization)
 

We first sort intervals which will cost O(n logn).
 
Then to save overlapping intervals and compare previous intervals, we need an extra list res.
 

def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        res = [intervals[0]]

 
 

Compare intervals)
 

Since we saved the 0th interval in res, we'll start comparing 1st interval with the 0th interval. 
 
To find if the two intervals overlap, we need to compare the current interval's start with the previous interval's end.
So we save the previous interval's end in a variable lastEnd.
 
If the current interval does overlap, we update the previous interval. 

1. Since intervals is already sorted, we know that res[-1][0] is less than or equal to start.
2. However, we do not know which interval's end is greater. Thus we use max function to update the overlapping interval's end properly.

 
If the current interval does NOT overlap, there's nothing to do with the previous interval. So we add the current interval to res for future comparisons.
 
 
Once all the intervals are merged, we return res which will contain merged intervals.
 

def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        res = [intervals[0]]

        for start, end in intervals[1:]:
            lastEnd = res[-1][1]

            if start <= lastEnd:
                res[-1][1] = max(lastEnd, end)
            else:
                res.append([start, end])
        
        return res

 
 
 
I also used a similar approach, but his way of handling numbers and output variable was much better than mine, so I wanted to study and use this approach for other problems.