56. Merge Intervals

[sophryu99]

56. Merge Intervals

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

1. Sort the given array by the first element in ascending order
2. Use a stack to add the elements, pop from the top when comparing
3. If there is an overlap, say prev[-1] >= curr[0], create a new interval with [min(prev[0], curr[0], max(prev[1], curr[1])] to cover the maximum range. Replace the top most interval with the new interval
4. Else, append the interval to the array

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # Sort by the first element asc 
        intervals.sort(key = lambda pairs: pairs[0])
        stck = [intervals[0]]

        for i in range(1, len(intervals)):
            prev = stck[-1]
            if prev[1] >= intervals[i][0]:
                new_interval = [min(prev[0], intervals[i][0]), max(prev[1], intervals[i][1])]
                stck[-1] = new_interval
            else:
                stck.append(intervals[i])

        return stck

N: array size

• Time Complexity: O(N) linear scan of the array
• Space Complexity: O(N) stack size