0056. 合并区间

题目地址(56. 合并区间)

https://leetcode-cn.com/problems/merge-intervals/

题目描述

给出一个区间的集合，请合并所有重叠的区间。 示例 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]

前置知识

排序

公司

阿里
腾讯
百度
字节

思路

先对数组进行排序，排序的依据就是每一项的第一个元素的大小。
然后我们对数组进行遍历，遍历的时候两两运算（具体运算逻辑见下）
判断是否相交，如果不相交，则跳过
如果相交，则合并两项

关键点解析

对数组进行排序简化操作
如果不排序，需要借助一些 hack,这里不介绍了

代码

语言支持: Javascript，Python3

/* * @lc app=leetcode id=56 lang=javascript * * [56] Merge Intervals *//** * @param {number[][]} intervals * @return {number[][]} */function intersected(a, b) {  if (a[0] > b[1] || a[1] < b[0]) return false;  return true;}function mergeTwo(a, b) {  return [Math.min(a[0], b[0]), Math.max(a[1], b[1])];}var merge = function (intervals) {  // 这种算法需要先排序  intervals.sort((a, b) => a[0] - b[0]);  for (let i = 0; i < intervals.length - 1; i++) {    const cur = intervals[i];    const next = intervals[i + 1];    if (intersected(cur, next)) {      intervals[i] = undefined;      intervals[i + 1] = mergeTwo(cur, next);    }  }  return intervals.filter((q) => q);};

Python3 Code:

class Solution:    def merge(self, intervals: List[List[int]]) -> List[List[int]]:        """先排序，后合并"""        if len(intervals) <= 1:            return intervals        # 排序        def get_first(a_list):            return a_list[0]        intervals.sort(key=get_first)        # 合并        res = [intervals[0]]        for i in range(1, len(intervals)):            if intervals[i][0] <= res[-1][1]:                res[-1] = [res[-1][0], max(res[-1][1], intervals[i][1])]            else:                res.append(intervals[i])        return res

复杂度分析

令 n 为 intervals 的长度。

时间复杂度：由于采用了排序，因此复杂度大概为 $O(nlogn)$
空间复杂度：$O(n)$

扩展

这道题是让你合并区间。这里还有一道删除区间的题目，大家可以结合起来练习Interval-Carving。

参考 Python3 代码：

class Solution:    def solve(self, intervals, cut):        ans = []        for s, e in intervals:            if s < cut[0]: ans.append([s, min(e, cut[0])])            if cut[1] < e: ans.append([max(s, cut[1]), e])        return ans

另外下面的图是我思考时候的草图，红色表示需要删除的区间，灰色是题目给的区间。