区间合并

贪心

说明

按起点排序后逐个扩展当前区间；时间 O(n log n)。

分析

按起点排序后，只需和当前合并区间比较：若重叠就扩展终点，否则把新区间放进结果。排序保证后续区间不可能回到已结束区间的左侧。

图解推演

补充 [1,3]、[2,6]、[8,10]，第二段与当前段重叠，将终点更新成 max(3,6)=6；第三段起点 8 超过当前终点，开启新段。遇到被包含的 [2,4] 时不能把终点从 6 缩回 4。是否合并端点相接的段由区间闭合约定决定。

查看图表代码

适用前提与边界

示例会原地排序输入切片；若调用方需要保留原顺序，应先复制。

示例输入与调用

fmt.Println(MergeIntervals([]Interval{{1, 3}, {2, 5}, {8, 9}}))

运行输出

[{1 5} {8 9}]

完整 Go 示例

package main

import (
	"fmt"
	"sort"
)

type Interval struct{ Start, End int }

func MergeIntervals(a []Interval) []Interval {
	sort.Slice(a, func(i, j int) bool { return a[i].Start < a[j].Start })
	out := []Interval{}
	for _, v := range a {
		if len(out) == 0 || v.Start > out[len(out)-1].End {
			out = append(out, v)
		} else if v.End > out[len(out)-1].End {
			out[len(out)-1].End = v.End
		}
	}
	return out
}

func main() {
	fmt.Println(MergeIntervals([]Interval{{1, 3}, {2, 5}, {8, 9}}))
}