LeetCode 56. 合并区间

Description

给出一个区间的集合，请合并所有重叠的区间。

示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2: 输入: [[1,4],[4,5]] 输出: [[1,5]] 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

Solution

class Solution(object): def merge(self, intervals): if not intervals: return [] intervals.sort(key=lambda x: (x[0], x[1])) ans = [] left, right = -1, -1 # 初始化，后序要pop掉 for i, e in enumerate(intervals): # 保证当前区间不是上一区间的子集 例如 （1，4）与（2，3）left为1，right为4 if e[0] <= right and e[1] > right: right = e[1] elif e[0] > right: # 当前区间与上一区间不相交 ans.append([left, right]) left = e[0] right = e[1] if i == len(intervals)-1: # 最后一次的left，right ans.append([left, right]) ans.pop(0) return ans