区间排序与调度
本节目标
根据目标选择右端点、左端点或当前覆盖边界，解决区间选点、分组与覆盖问题。
同样是区间，目标不同就要维护不同的不变量：选最少点时尽量早结束；分最少组时复用最早结束的组；覆盖目标时每步尽量向右延伸。
识别信号
- 输入由许多一维区间组成，关键在于端点的相对顺序。
- 问“最少选多少点”“最少分几组”或“最少用几段覆盖目标”。
- 排序以后，当前决策可以用一个右端点、一个小根堆或一个已覆盖前缀概括。
问题模型与核心不变量
把 AcWing 三题都看成闭区间 [l,r]。因此端点相等时两个区间相交：选到 r 能覆盖从 l 到 r 的全部位置；一个组只有在旧区间右端点严格小于新区间左端点时才可复用。
区间选点按右端点升序；遇到尚未覆盖的当前最早结束区间时，选择它的右端点，也就是在该区间内尽可能靠右地落点，以最大化后续区间仍可被覆盖的机会。区间分组按左端点升序，小根堆保存每个组最后一个闭区间的右端点。区间覆盖则维护已经连续覆盖到的最右位置，每轮从所有左端点不超过它的候选中取最远右端点；没有进展就存在缺口。
通用模板
选点：按 r 升序；若最后选点 < l，就在当前区间内尽可能靠右地选 r
分组：按 l 升序；若最小组尾 < l，弹出并复用；压入 r
覆盖：在 l <= covered 的全部区间中找最大 r；若不增大 covered，失败
模板变体
- 选点的“最后选点”可替换为上次保留区间的结束位置，得到最多不相交区间。
- 分组的堆大小就是同时相交的闭区间最大数量；若端点不相交的定义改为半开区间
[l,r)，复用条件改为top <= l。 - 覆盖模型只要求覆盖正长度目标线段
[left,right]；目标为空或反向（left >= right）时按本教程约定不需要区间，返回0。
母题序列
常见误区
- 未声明端点是闭还是开，导致端点相等时选点、分组的判断相互矛盾。
- 区间覆盖只选第一个可接续区间，而没有比较所有候选的最远右端点。
- 分组堆放入所有历史区间而不弹出已可复用的组尾。
- 将划分字母区间误做成每个字符单独分段，忽略后续出现会扩张当前边界。
迁移方向
先写出“当前状态究竟代表什么”：一个选点、最早组尾，还是连续覆盖前缀。题目换成无重叠区间或用最少数量的箭引爆气球时，仍从区间选点的右端点排序与交换论证迁移，而不另记一套无关模板。