扫描线基础

计算几何

说明

按坐标排序事件并维护当前活跃状态；下例统计半开区间最大重叠数。

分析

把区间起点当作 +1 事件、终点当作 −1 事件，按坐标排序后依次更新活跃区间数。相同坐标时先处理终点，符合半开区间 [start,end) 不在端点重叠的定义。

图解推演

区间 [1,4)、[2,5)、[5,6) 的活跃数随事件为 1、2、1、0、1、0，最大值 2。在坐标 5，先处理第二段的终点再处理第三段的起点，避免虚构重叠。零长区间应忽略或单独约定，不能当成有持续时间的活动。

查看图表代码

适用前提与边界

最大活跃数就是最大并发覆盖数量。

示例输入与调用

fmt.Println(MaxOverlap([]Interval{{1, 4}, {2, 5}, {5, 6}}))

运行输出

2

完整 Go 示例

package main

import (
	"fmt"
	"sort"
)

type Interval struct{ Start, End int }

func MaxOverlap(a []Interval) int {
	type Event struct{ At, Delta int }
	events := []Event{}
	for _, v := range a {
		events = append(events, Event{v.Start, 1}, Event{v.End, -1})
	}
	sort.Slice(events, func(i, j int) bool {
		if events[i].At == events[j].At {
			return events[i].Delta < events[j].Delta
		}
		return events[i].At < events[j].At
	})
	active, best := 0, 0
	for _, e := range events {
		active += e.Delta
		best = max(best, active)
	}
	return best
}

func main() {
	fmt.Println(MaxOverlap([]Interval{{1, 4}, {2, 5}, {5, 6}}))
}