Description

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

Solution

首先按照开始time进行排序，然后遍历看如果cur.start < last.start则merge

Time O(NlogN)
Space O(N)

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        if len(intervals)==0 :
            return []
        s_inter = sorted(intervals, key= lambda x: x[0])
        res =[]
        end = None
        start = None
        for i in s_inter:
            if end is None:
                end = i[1]
                start = i[0]
            else:
                if i[0] <= end :
                    if i[1] > end: # 关键判断条件
                        end = i[1]
                else:
                    res.append([start,end])
                    start = i[0]
                    end = i[1]
        res.append([start,end])
        return res
                
   

更简洁的写法

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        s_inter = sorted(intervals)
        res = []
        for i in s_inter:
            if len(res)== 0 or i[0] > res[-1][1]:
                res.append(i)  # 直接insert interval, 然后update [-1][1]
            else:
                res[-1][1] = max(i[1], res[-1][1] )
        return res