区间调度

贪心

说明

按结束时间从早到晚选择不冲突区间；得到最多可安排的活动数。

分析

把活动按结束时间排序，优先选择最早结束且不与上一个活动冲突的区间。较早结束会给后续活动留下最多可用空间，这可用交换论证证明最优。

图解推演

补充活动 A=[1,3)、B=[2,5)、C=[3,4)，按结束时间选 A 再选 C，共 2 个。任意最优方案的首活动都可替换成更早结束的 A，而不挤占后续时间，这给出交换论证。若活动有不同收益，最多数量与最大收益是不同目标，不能继续用同一贪心。

查看图表代码

适用前提与边界

示例把区间视为允许端点相接；是否相接算冲突须按业务定义。

示例输入与调用

fmt.Println(MaxActivities([]Interval{{1, 3}, {2, 4}, {3, 5}}))

运行输出

2

完整 Go 示例

package main

import (
	"fmt"
	"sort"
)

type Interval struct{ Start, End int }

func MaxActivities(a []Interval) int {
	sort.Slice(a, func(i, j int) bool { return a[i].End < a[j].End })
	end, count := int(^uint(0)>>1)*-1-1, 0
	for _, v := range a {
		if v.Start >= end {
			count++
			end = v.End
		}
	}
	return count
}

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