56. Merge Intervals (Python)

Related Topic

Array.

Description

Given a collection of intervals, merge all overlapping intervals.

Sample I/O

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.

Methodology

Sort the given array by the first value of each element in ascending order then iterate the new sorted array. If the current element’s first value is smaller than last element’s second value then there is overlaping and we need to determine the new boundary which left boundary will be last element’s first value and right boundary will be the max value from last element’s second value and current element’s second value.

def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if len(intervals) == 0:
            return []
        sorted_intervals = sorted(intervals, key = lambda x: x[0])
        res = [sorted_intervals[0]]
        for interval in sorted_intervals[1:]:
            #the next node's smallest value is smaller than the prev node's largest value, then overlapping
            if interval[0] <= res[-1][1]:
                #left boundary is the largest value
                res[-1][1]=max(interval[1], res[-1][1])
            else:
                res.append(interval)
        return res

BigO

We iterate the list once so the total cost will be O(nlogn) because the sort function in python is O(nlogn)