合并区间

怎样从“intervals=[[1,3],[2,6],[8,10],[15,18]],合并重叠区间。”推导出 区间 · 合并，并证明每次状态变化都不会漏掉答案？

中心结论：按 start 排序;结果尾与当前比:重叠则扩展尾,否则 push 新区间。

合并给的多个区间，区间有重叠的要进行区间合并。

在本站主例中，intervals=[[1,3],[2,6],[8,10],[15,18]],合并重叠区间。

算法最终需要得到或观察：[[1,6],[8,10],[15,18]]。

两两比较所有区间会重复检查重叠关系；排序后只需维护当前已合并边界或上一个结束点。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“区间时间轴”，明确答案需要观察什么。
2. 2状态只维护 排序后扫描、结果尾 [s,e]。
3. 3转移每一步按照 按 start 排序;结果尾与当前比:重叠则扩展尾,否则 push 新区间。
4. 4收尾读取 [[1,6],[8,10],[15,18]]。，并复核边界与复杂度。

排序把二维的任意关系压缩成从左到右的一次扫描。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：排序后扫描、结果尾 [s,e]。

先按照区间起点进行排序。然后从区间起点小的开始扫描，依次合并每个有重叠的区间。

按 start 排序;结果尾与当前比:重叠则扩展尾,否则 push 新区间。

执行过程中持续维护：排序后扫描、结果尾 [s,e]。

正确性依赖以下不变量：处理完前 i 个区间后，res 中保存的是这些区间合并后的结果；res 内部从左到右排列，并且互不重叠。

面试时可以压缩为：按 start 排序 O(n log n)；线性扫描 O(n)：cur 只与 res 尾 last 比，若 cur.start<=last.end 则 last.end=max，否则 append；不计输出时额外 O(1)，计 res 则 O(n)。

落到当前题，执行机制可以压缩为：按 start 排序;结果尾与当前比:重叠则扩展尾,否则 push 新区间。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入intervals=[[1,3],[2,6],[8,10],[15,18]],合并重叠区间。 因为：按 start 排序;结果尾与当前比:重叠则扩展尾,否则 push 新区间。
2. 2区间 [1,3] 独立把当前区间压入结果栈。 因为：不重叠的区间必须保留为独立段。
3. 3压入新区间更新合并结果。 因为：线性扫描一遍,每个区间最多进出栈一次,O(n log n)。
4. 4区间 [2,6] 与栈顶重叠扩展栈顶区间的右端点。 因为：合并后仍覆盖两段区间的并集,且右端取 max。
5. 5区间 [8,10] 独立把当前区间压入结果栈。 因为：不重叠的区间必须保留为独立段。
6. 6区间 [15,18] 独立把当前区间压入结果栈。 因为：不重叠的区间必须保留为独立段。
7. 7压入新区间更新合并结果。 因为：线性扫描一遍,每个区间最多进出栈一次,O(n log n)。
8. 8收尾与复杂度[[1,6],[8,10],[15,18]]。 因为：时间 O(n log n) · 空间 O(n)。按 start 排序;结果尾与当前比:重叠则扩展尾,否则 push 新区间。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// Interval define
type Interval = structures.Interval

/**
 * Definition for an interval.
 * type Interval struct {
 *	   Start int
 *	   End   int
 * }
 */

func merge(intervals []Interval) []Interval {
	if len(intervals) == 0 {
		return intervals
	}
	quickSort(intervals, 0, len(intervals)-1)
	res := make([]Interval, 0)
	res = append(res, intervals[0])
	curIndex := 0
	for i := 1; i < len(intervals); i++ {
		if intervals[i].Start > res[curIndex].End {
			curIndex++
			res = append(res, intervals[i])
		} else {
			res[curIndex].End = max(intervals[i].End, res[curIndex].End)
		}
	}
	return res
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a int, b int) int {
	if a > b {
		return b
	}
	return a
}

func partitionSort(a []Interval, lo, hi int) int {
	pivot := a[hi]
	i := lo - 1
	for j := lo; j < hi; j++ {
		if (a[j].Start < pivot.Start) || (a[j].Start == pivot.Start && a[j].End < pivot.End) {
			i++
			a[j], a[i] = a[i], a[j]
		}
	}
	a[i+1], a[hi] = a[hi], a[i+1]
	return i + 1
}
func quickSort(a []Interval, lo, hi int) {
	if lo >= hi {
		return
	}
	p := partitionSort(a, lo, hi)
	quickSort(a, lo, p-1)
	quickSort(a, p+1, hi)
}

func main() {
    // 1. 主例
    //    输入：mode="merge-intervals", intervals=[[1,3],[2,6],[8,10],[15,18]]
    //    期望：[[1,6],[8,10],[15,18]]。
    //
    // 2. 失败 / 未命中
    //    检查：未排序直接 merge 会漏重叠。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC57 插入区间；LC435 无重叠区间
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意intervals=[[1,3],[2,6],[8,10],[15,18]],合并重叠区间。
2. 2重复两两比较所有区间会重复检查重叠关系；排序后只需维护当前已合并边界或上一个结束点。
3. 3优化按 start 排序;结果尾与当前比:重叠则扩展尾,否则 push 新区间。
4. 4证明处理完前 i 个区间后，res 中保存的是这些区间合并后的结果；res 内部从左到右排列，并且互不重叠。
5. 5复杂度时间 O(n log n)，空间 O(n)