【Leetcode56】合并区间（数组 | 排序）

一、题目

二、思路

• 先将所有子列表按照start_pos进行排序，有利于保持顺序性，每次处理新子列表时，只用和结果列表ans_lst的最后一个子列表对比，如果有重合则合并，然后将合并的新子列表插入结果列表
• 排序可以使用lambda函数，intervals.sort(key=lambda x: x[0])
• 因为使用了sort，所以时间复杂度O(nlogn)，空间复杂度O(n)

三、代码

class Solution(object):def merge(self, intervals):""":type intervals: List[List[int]]:rtype: List[List[int]]"""ans_lst = []intervals.sort(key=lambda x: x[0])for i in range(len(intervals)):this_lst = intervals[i]if i == 0:ans_lst.append(this_lst)continueelse:# 从第二个子列表开始past_lst = ans_lst[-1]if past_lst[1] >= this_lst[0]:# 有重叠new_one_lst = [min(past_lst[0], past_lst[1], this_lst[0], this_lst[1]), max(past_lst[0], past_lst[1], this_lst[0], this_lst[1])]ans_lst.pop()ans_lst.append(new_one_lst)else:# 没有重叠ans_lst.append(this_lst)return ans_lst