[leetcode] 56. Merge Intervals

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

 

class Solution(object):
    def merge(self, intervals):
        intervals.sort()
        if len(intervals) <2:
            return intervals
        
        first = intervals[0]
        result = []
        for interval in intervals:
            if interval[0] > first[1]:
                result.append(first)
                first = interval
            else :
                first[1]= max(first[1],interval[1])
        result.append(first)
        return result