LeetCode 56. Merge Intervals

Description

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

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[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: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Explanation

base on start and end to merge interval

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