56. 合并区间

Difficulty: 中等

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start<sub style="display: inline;">i</sub>, end<sub style="display: inline;">i</sub>] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 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] 可被视为重叠区间。

提示：

• 1 <= intervals.length <= 10<sup>4</sup>
• intervals[i].length == 2
• 0 <= start<sub style="display: inline;">i</sub> <= end<sub style="display: inline;">i</sub> <= 10<sup>4</sup>

Solution

两个区间有交集的条件是排序区间的最后一个区间的最后一个元素比待放入区间的第一个元素大，比如[1,4]和[3,6]，时间复杂度为O(n)。

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if not intervals:
            return []
        # 按照intervals中元素中第一个数字排序
        intervals.sort(key=lambda x: x[0])
        res = []
        for item in intervals:
            # 如果没有交集，直接放入res中
            if not res or res[-1][1] < item[0]:
                res.append(item)
            else:
                # 如果有交集
                res[-1][1] = max(res[-1][1],item[1])
        return res

# runtime:44 ms
# memory:15.6 MB