56. 合并区间

力扣题目链接 (opens new window)

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

示例 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^4
• intervals[i].length == 2
• 0 <= start_i <= end_i <= 10^4

算法公开课

《代码随想录》算法视频公开课 (opens new window)：贪心算法，合并区间有细节！LeetCode：56.合并区间 (opens new window)，相信结合视频在看本篇题解，更有助于大家对本题的理解。

思路

暴力解法

这道题最直观的思路是什么？暴力！

枚举所有区间的组合，判断两个区间是否重叠，重叠就合并。但合并后的新区间可能又和别的区间重叠，需要反复遍历，时间复杂度 O(n^2)，而且实现起来很麻烦。

排序 + 贪心

这道题的本质其实还是判断重叠区间问题。

和之前做过的 452. 用最少数量的箭引爆气球 (opens new window) 和 435. 无重叠区间 (opens new window) 都是一个套路。

这几道题都是判断区间重叠，区别就是判断区间重叠后的逻辑不同，本题是判断区间重叠后要进行区间合并。

所以一样的套路，先排序，让所有的相邻区间尽可能的重叠在一起，按左边界，或者右边界排序都可以，处理逻辑稍有不同。

按照左边界从小到大排序之后，如果 intervals[i][0] <= intervals[i - 1][1]，即 intervals[i] 的左边界 <= intervals[i - 1] 的右边界，则一定有重叠。（本题相邻区间也算重叠，所以是 <=）

这么说有点抽象，看图：（注意图中区间都是按照左边界排序之后了）

关键问题

如何去模拟合并区间呢？

其实就是用合并区间后左边界和右边界，作为一个新的区间，加入到 result 数组里就可以了。如果没有合并就把原区间加入到 result 数组。

具体来说：

• 用 result 数组记录合并后的区间，先把第一个区间放进去
• 遍历后续区间时，和 result 的最后一个区间比较
• 如果重叠，更新 result 最后一个区间的右边界（取最大值）
• 如果不重叠，直接把当前区间加入 result

为什么合并时只需要更新右边界？

因为我们按照左边界排序的，result 最后一个区间的左边界一定是最小的，只需要看右边界是否需要扩展就行。

算法流程

1. 对 intervals 按左边界从小到大排序
2. 将第一个区间加入 result
3. 遍历 intervals[1:]：
   • 如果当前区间的左边界 <= result 最后一个区间的右边界 → 重叠，更新右边界
   • 否则 → 不重叠，将当前区间加入 result
4. 返回 result

让我们用题目示例 intervals = [[1,3],[2,6],[8,10],[15,18]] 来一步步模拟：

1. 排序后：[[1,3],[2,6],[8,10],[15,18]]
2. result = [[1,3]]
3. [2,6]：左边界 2 <= 3，重叠，更新右边界 max(3,6)=6，result = [[1,6]]
4. [8,10]：左边界 8 > 6，不重叠，加入 result = [[1,6],[8,10]]
5. [15,18]：左边界 15 > 10，不重叠，加入 result = [[1,6],[8,10],[15,18]]

最终结果：[[1,6],[8,10],[15,18]]

代码实现

C++代码如下：

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> result;
        if (intervals.size() == 0) return result;
        // 按左边界排序
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});

        // 第一个区间放进结果集，后面如果重叠就在result上直接合并
        result.push_back(intervals[0]);

        for (int i = 1; i < intervals.size(); i++) {
            if (result.back()[1] >= intervals[i][0]) { // 发现重叠区间
                // 合并区间，只更新右边界就好，因为result.back()的左边界一定是最小值
                result.back()[1] = max(result.back()[1], intervals[i][1]);
            } else {
                result.push_back(intervals[i]); // 区间不重叠
            }
        }
        return result;
    }
};

• 时间复杂度: O(nlogn)，排序的时间开销
• 空间复杂度: O(logn)，排序需要的空间开销

代码详解

录友们可能会有几个疑问：

1. 为什么按左边界排序？

按左边界排序后，当前区间的左边界一定 >= 前一个区间的左边界。所以我们只需要判断当前区间的左边界是否 <= 前一个区间的右边界，就能确定是否重叠。如果按右边界排序也行，但处理逻辑稍有不同。

2. 重叠的判断条件为什么是 >= 而不是 >？

因为本题中，相邻的区间也算重叠。比如 [1,4] 和 [4,5]，右边界 4 和左边界 4 相等，这种情况下应该合并为 [1,5]。如果用 >，就会漏掉这种情况。

3. 合并时为什么只更新右边界？

因为按照左边界排序后，result 中最后一个区间的左边界一定 <= 当前区间的左边界，所以左边界不需要更新，只需要看右边界是否需要扩展。

4. 为什么先把第一个区间放入 result？

这样在遍历时，每次都和 result 的最后一个区间比较，逻辑统一。如果 result 为空就直接加入，后续重叠就合并，不重叠就追加。

扩展

区间问题三连

这道题和 452. 用最少数量的箭引爆气球 (opens new window)、435. 无重叠区间 (opens new window) 是同一套路，都是先排序再处理重叠，区别在于发现重叠后的操作：

题目	发现重叠后的操作
452.用最少数量的箭引爆气球	更新右边界为较小值
435.无重叠区间	计数需要移除的区间
56.合并区间	合并为新区间

录友们可以把这三道题一起做一下，体会一下套路。

按右边界排序

按左边界排序是最直观的，但按右边界排序也可以。按右边界排序后，只需要记录当前最右边界，遍历时判断当前区间的左边界是否 <= 最右边界，如果是则更新最右边界为 max(最右边界, 当前右边界)。

其他语言版本

Java：

class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> res = new LinkedList<>();
        // 按左边界排序
        Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0]));
        int start = intervals[0][0];
        int rightmostRightBound = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] > rightmostRightBound) {
                // 不重叠，加入区间，更新start
                res.add(new int[]{start, rightmostRightBound});
                start = intervals[i][0];
                rightmostRightBound = intervals[i][1];
            } else {
                // 重叠，更新最大右边界
                rightmostRightBound = Math.max(rightmostRightBound, intervals[i][1]);
            }
        }
        res.add(new int[]{start, rightmostRightBound});
        return res.toArray(new int[res.size()][]);
    }
}

Python：

class Solution:
    def merge(self, intervals):
        result = []
        if len(intervals) == 0:
            return result
        # 按照区间的左边界进行排序
        intervals.sort(key=lambda x: x[0])
        # 第一个区间可以直接放入结果集中
        result.append(intervals[0])
        for i in range(1, len(intervals)):
            if result[-1][1] >= intervals[i][0]:  # 发现重叠区间
                # 合并区间，只需要更新右边界
                result[-1][1] = max(result[-1][1], intervals[i][1])
            else:
                result.append(intervals[i])  # 区间不重叠
        return result

Go：

func merge(intervals [][]int) [][]int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    res := make([][]int, 0, len(intervals))
    left, right := intervals[0][0], intervals[0][1]
    for i := 1; i < len(intervals); i++ {
        if right < intervals[i][0] {
            res = append(res, []int{left, right})
            left, right = intervals[i][0], intervals[i][1]
        } else {
            right = max(right, intervals[i][1])
        }
    }
    res = append(res, []int{left, right})
    return res
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

JavaScript：

var merge = function(intervals) {
    intervals.sort((a, b) => a[0] - b[0]);
    let prev = intervals[0];
    let result = [];
    for (let i = 0; i < intervals.length; i++) {
        let cur = intervals[i];
        if (cur[0] > prev[1]) {
            result.push(prev);
            prev = cur;
        } else {
            prev[1] = Math.max(cur[1], prev[1]);
        }
    }
    result.push(prev);
    return result;
};

TypeScript：

function merge(intervals: number[][]): number[][] {
    const resArr: number[][] = [];
    intervals.sort((a, b) => a[0] - b[0]);
    resArr[0] = [...intervals[0]];
    for (let i = 1, length = intervals.length; i < length; i++) {
        const interval = intervals[i];
        const last = resArr[resArr.length - 1];
        if (interval[0] <= last[1]) {
            last[1] = Math.max(interval[1], last[1]);
        } else {
            resArr.push([...intervals[i]]);
        }
    }
    return resArr;
};

Rust：

impl Solution {
    pub fn merge(mut intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let mut res = vec![];
        if intervals.is_empty() {
            return res;
        }
        intervals.sort_by_key(|a| a[0]);
        res.push(intervals[0].clone());
        for interval in intervals.into_iter().skip(1) {
            let res_last_ele = res.last_mut().unwrap();
            if res_last_ele[1] >= interval[0] {
                res_last_ele[1] = interval[1].max(res_last_ele[1]);
            } else {
                res.push(interval);
            }
        }
        res
    }
}

C：

#define max(a, b) ((a) > (b) ? (a) : (b))

// 根据左边界进行排序
int cmp(const void *var1, const void *var2) {
    int *v1 = *(int **)var1;
    int *v2 = *(int **)var2;
    return v1[0] - v2[0];
}

int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes) {
    int **result = malloc(sizeof(int *) * intervalsSize);
    *returnColumnSizes = malloc(sizeof(int) * intervalsSize);
    for (int i = 0; i < intervalsSize; i++) {
        result[i] = malloc(sizeof(int) * 2);
    }
    qsort(intervals, intervalsSize, sizeof(int *), cmp);
    int count = 0;
    for (int i = 0; i < intervalsSize; i++) {
        int L = intervals[i][0], R = intervals[i][1];
        if (count == 0 || result[count - 1][1] < L) {
            returnColumnSizes[0][count] = 2;
            result[count][0] = L;
            result[count][1] = R;
            count++;
        } else {
            result[count - 1][1] = max(R, result[count - 1][1]);
        }
    }
    *returnSize = count;
    return result;
}