LeetCode 56. 合并区间

Categories:

Tags:

题目描述
思路分析
1. 解法一：排序 + 贪心合并（推荐）
相似题目

题目描述

✅ 56. 合并区间

题目：

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

示例 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 <= starti <= endi <= 10^4

思路分析

解法一：排序 + 贪心合并（推荐）

核心思路：

按起点对所有区间升序排序后，只需将当前区间与结果集末尾区间比较：

cur[0] > last[1]：无重叠，直接将 cur 加入结果集

cur[0] ≤ last[1]：有重叠，合并，更新 last[1] = max(last[1], cur[1])

为什么只比较末尾：排序后起点单调不减，当前区间不可能与结果集中更早的区间重叠。

注意：合并时取 max(last[1], cur[1]) 而不是 cur[1]，因为 cur 可能完全被 last 包含（如 [1,10] 和 [2,5]）。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示区间数量。

空间复杂度：O(n)，其中 n 表示结果集大小。

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> res = new ArrayList<>();
        res.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            int[] last = res.get(res.size() - 1);
            if (intervals[i][0] <= last[1]) {
                // 合并：扩展末尾
                last[1] = Math.max(last[1], intervals[i][1]);
            } else {
                // 无重叠，直接加入
                res.add(intervals[i]);
            }
        }
        return res.toArray(new int[0][]);
    }
}

func merge(intervals [][]int) [][]int {
	if len(intervals) <= 1 {
		return intervals
	}

	// 按照区间的起始值进行排序
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})

	var res [][]int
	res = append(res, intervals[0])

	for _, cur := range intervals[1:] {
		pre := res[len(res)-1]
		if cur[0] > pre[1] {
			// 当前区间不重叠，直接添加
			res = append(res, cur)
		} else {
			// 当前区间重叠，合并：扩展末尾
			pre[1] = max(pre[1], cur[1])
		}
	}

	return res
}

相似题目

题目	难度	考察点
57. 插入区间	中等	区间插入合并
252. 会议室	简单	区间排序
253. 会议室 II	中等	贪心、堆
495. 提莫攻击	简单	区间合并模拟
763. 划分字母区间	中等	贪心、区间合并
986. 区间列表的交集	中等	双指针区间求交
2276. 统计区间中的整数数目	困难	区间合并、有序集合
2406. 将区间分为最少组数	中等	贪心、堆
2446. 判断两个事件是否存在冲突	简单	区间判断
3169. 无会议的工作日	中等	区间合并
435. 无重叠区间	中等	贪心、最少删除不重叠

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/35203621