56-合并区间

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

---

示例

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

---

解法

核心思想：按左端点排序后，判断后一个的起始点是否包含在前一个区间中

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        n = len(intervals)
        if n < 2:
            return intervals
        res = []
        intervals.sort()
        for i in range(n-1):
            # 后一个区间中包含在前一个区间内的元素
            if intervals[i + 1][0] in range(intervals[i][0], intervals[i][1] + 1):
                # 新的区间范围
                l1, l2 = intervals[i][0], max(intervals[i][1], intervals[i+1][1])
                intervals[i+1] = [l1, l2]
                intervals[i] = "*"
        res = [ i for i in intervals if i != "*" ]
        return res

---

相关信息

LeetCode：Discussion | Solution