Problem Statement in English

You’re given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Approach

There are 2 solutions here, both with the same time complexity ($O(n \log n)$). One uses extra space and the other uses constant space.

I personally find the constant space solution more intuitive and easier to understand, so we’ll start from there.

Constant Space

The idea is to sort the intervals by their start time. Then, we can iterate through the sorted intervals, while maintaining a buffer interval that tells us the current merged interval, and merge them if they overlap.

The way we merge them is by checking if the end of the buffer interval is greater than or equal to the start of the current interval. If they overlap, we update the end of the buffer interval to be the maximum of the two ends. If they don’t overlap, we add the buffer interval to our result and update the buffer to be the current interval.

Remember to add the last buffer interval to the result after the loop.

Extra Space

This solution uses a dictionary to keep track of the start and end points of the intervals.

We increment the count at the start point and decrement it at the end point.

Then, we iterate through the sorted keys of the dictionary, maintaining a count of overlapping intervals.

When the count is 0, we mark the start of a new merged interval, and when it goes back to 0, we mark the end of that merged interval — using the start, and current location to create the merged interval.

And we’re done!

Solution in Python

  • Extra Space ($O(n)$ space)

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        ans = []
        db = defaultdict(int)

        for start, end in intervals:
            db[start]+=1
            db[end]-=1

        start = 0
        count = 0
        for location in sorted(db):
            if count == 0:
                start = location
            
            count+=db[location]

            if count == 0:
                ans.append((start, location))
            
        return ans
  • Constant Space ($O(1)$ space)

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

        for start, stop in intervals:
            if buffer[1] < start:
                res.append(buffer.copy())
                buffer[0], buffer[1] = start, stop
            elif buffer[1] < stop:
                buffer[1] = stop
            
        res.append(buffer)

        return res

Mistakes I Made

And we are done.