LeetCode LCR 074. 合并区间

Categories:

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

题目描述

✅ LCR 074. 合并区间

思路分析

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

核心思路：

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

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)，结果集大小

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	中等	贪心、堆
435. 无重叠区间	中等	贪心，最少删除不重叠
986. 区间列表的交集	中等	双指针区间求交

本文作者: HGNULB

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