问题描述

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

示例 1:

输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。

提示：

intervals[i][0] <= intervals[i][1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-intervals
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

先对 intervals 中的元素进行排序，排序规则是：

• 如果 element1 中的第一个元素大于 element2 中的第一个元素，那么 element1 > element2
• 如果 element1 中的第一个元素等于 element2 中的第一个元素：
  • 如果 element1 中的第二个元素大于 element2 中的第二个元素，则 element1 > element2
  • 如果 element1 中的第二个元素等于 element2 中的第二个元素，则 element1 == element2
  • 如果 element1 中的第二个元素小于 element2 中的第二个元素，则 element1 < element2
• 否则 element1 < element2

然后顺序遍历每个区间 interval，直到最后一个区间：

• 如果 interval 的左边缘与当前区间的右边缘重叠，那么将其合并到当前区间，合并规则是：
  • 当前区间的左边缘不变
  • 当前区间的右边缘置为max(当前区间的右边缘，interval 的右边缘)
• 否则输出当前区间，把 interval 当作当前区间

Python 实现

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        if not intervals or len(intervals) == 1:
            return intervals

        intervals.sort()

        ret = []
        current_left = intervals[0][0]
        current_right = intervals[0][1]
        for ind, (left, right) in enumerate(intervals[1:], start=1):
            if left <= current_right:
                current_right = max(right, current_right)
            else:
                ret.append([current_left, current_right])
                current_left = left
                current_right = right
            if ind == len(intervals) - 1:
                ret.append([current_left, current_right])

        return ret