56. Merge Intervals

Description

See: https://leetcode.com/problems/merge-intervals/

Solution

LeetCode's solution

https://leetcode.com/problems/merge-intervals/solution/

Note: the merge may occur on more than two items. For example:

[[1,3], [1,2], [3,4], [6,10]] -> [[1,4], [6,10]]

My Solution

Strategy

Sort the array, this will put the intervals in ascending order.

Example: [[1,3], [6,10], [3,4], [1,2]] -> [[1,2], [1,3], [3,4], [6,10]]

This allows us to compare adjacent cells to see if they overlap.

So, if we have two pairs [x1, y1] and [x2, y2], we need to compare x1 and y2. If x1 <= y2 then the two pairs overlap and can be merged. The merge interval will be x1 and then the max of y1 and y2: [x1,max(y1,y2)]

Otherwise, the pairs do not overlap and the pair can just be appended to the result array. We always need to compare against the tail of the array as we merge the pairs into the tail of the result array.

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

Time complexity: O(n log n) - this is from the sort operation. There is one loop which is O(n), so the above code is O(n log n) + O(n), but this reduces to O(n log n).

Space complexity: worst case is O(n) which is from the Timsort sorting algorithm used by Python.

What I learned

To merge items, add the first item to the result array. Then iterate through the list and either update the tail item in the result array or append a the item to the result array.

This is easier than trying to handle the merge by taking two items from the array, merging them and then inserting into the array. This was convoluted when I needed to then compare the merged item to the next item in the array. I figured out that I needed to sort the array in order to compare the items.