56. 合并区间

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

解法一:

先按起点排序,然后逐个插入结果集,看当前区间的start是否大于结果集最后一个区间的end,若符合则插入作为新的区间;若不符合,说明交叠,判断当前区间的end是否大于结果集最后区间的end,若大于则更新结果集

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        #intervals每个元素为长度2的list,0号表示start,1号表示end
        intervals.sort(key = lambda x : x[0])    #先排序
        merge = []
        for interval in intervals:
            if not merge or merge[-1][1] < interval[0]:    #没有交叠
                merge.append(interval)
            else:
                merge[-1][1] = max(merge[-1][1], interval[1]) #若当前区间end更大,更新end
        return merge

最后更新于