合并区间

Leetcode Link: 56. 合并区间 - 力扣（LeetCode）

题目

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start_i, end_i] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

解法一

思路：贪心，每次遇到相邻的都合并

思路同无重叠区间和用最少数量的箭引爆气球

区别在于本题的 cover 不是交集，而是取并集

本题关键在于刚开始的排序。

题解：

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key = lambda x: (x[0], x[1]))
        cover = intervals[0]
        res = []
        for val in intervals[1:]:
            if cover[1] >= val[0]:
	            # 这里需要注意要取最大的，开始直接 =val[1] 了
	            # 有可能前一个结束位置比当前的结束位置还靠后
	            # 如 [[1, 4], [2, 3]]
                cover[1] = max(val[1], cover[1])
            else:
                res.append(cover)
                cover = val
        res.append(cover)
        return res

复习时更简化的写法，可以省略掉cover变量。

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        nums = sorted(intervals, key = lambda x: (x[0], -x[1]))
        res = [nums[0]] # 添加第一个作为初始化
        for val in nums[1:]:
            # 如果当前的头(val[0])比结尾的尾巴小，说明覆盖，则更新
            if val[0] <= res[-1][1]: 
                res[-1][1] = max(res[-1][1], val[1])
            else: # 反之说明不重叠，则直接append
                res.append(val)
        
        return res

启发和联系

相关题目：无重叠区间，用最少数量的箭引爆气球