LeetCode 56. Merge Intervals

Description

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

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.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Constraints:

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

Explanation

First sorted the interval base on the start of elements. Then compare each interval start and end with the last merged interval to decide whether to merge.

Python Solution

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

• Time complexity: ~ N
• Space complexity: ~1