每日一道算法题--leetcode 56--合并区间--python

503 阅读1分钟

【题目描述】

【思路解析】

1.按照intervals中每个列表中第一个元素从小到大进行排序

2.建立一个新列表re,用于保存结果

3.遍历intervals,当re中最后一个元素的尾部值小于当前interval的头部值,说明不重合,直接将该数组加入re;否则,更新re[-1][1],取max(re[-1][1],interval[1]).

【代码】

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x:x[0])
        re=[]
        for interval in intervals:
            if not re or re[-1][1]<interval[0]:
                re.append(interval)
            else:
                re[-1][1]=max(re[-1][1],interval[1])
        return re
时间复杂度O(nlogn)主要花费在sort上,空间复杂度在O(1)-O(n)。