MUYANG GUO / INDEX

LeetCode

LeetCode 56 Merge Intervals - Medium

56. Merge Intervals

·1 min read·#LeetCode#Medium#Python

56. Merge Intervals — Medium

Open on LeetCode

Problem

  1. 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.

Solution

class Solution:
    def merge(self, intervals):
        intervals.sort()
        res = []
        for interval in intervals:
            self.push_back(interval, res)
        return res
        
    def push_back(self, interval, res):
        if not res:
            res.append(interval)
            return 
        last_interval = res[-1]
        end_boundary = last_interval[-1]
        if end_boundary < interval[0]:
            res.append(interval)
            return
        
        res[-1][-1] = max(res[-1][-1], interval[-1])

Comments