[LeetCode]56. 合并区间（Merge Intervals）

题目描述

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

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

解题思路

排序。排序后所有可以合并的区间都是相邻的，使用队列来存储已经合并了的区间，判断当前区间与队尾区间是否可以合并时只需判断当前区间的左端点是否小于等于队尾区间的右端点即可。

代码

Python 3.6

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        queue = []
        for cur in intervals:
            while queue:
                last = queue.pop()
                if cur[0] <= last[1]:
                    cur[0], cur[1] = last[0], max(cur[1], last[1])
                else:
                    queue.append(last)
                    break
            queue.append(cur)
        return queue

执行用时 : 128 ms
内存消耗 : 15.6 MB