贪心区间选择与双指针配对 | WRC Youth Algorithm Lab

贪心不是“随便贪一下”，而是先证明某个局部决策不会破坏全局最优，再把这个决策重复到底。初中组里最典型的两类贪心题，就是区间调度和排序后双指针配对。它们的共性是：先把数据排出一种对决策最有利的顺序，然后每一步都做一个不会后悔的选择。

学习目标

学会识别什么时候适合用贪心，而不是回溯、DP 或暴力。
学会区分“结束时间优先的区间选择”和“最轻配最重的双指针配对”。
学会理解为什么这些局部策略是正确的。
学会在贪心过程中顺手维护额外统计量。

什么情况下该优先考虑贪心

题目通常有这些特征：

目标是最大化可选数量、最小化容器数、最小化冲突数。
每一步选择都会缩小后续可选范围。
一旦按某个规则排序后，后续决策只依赖边界位置。

如果题目还要求复杂的容量组合、自由回退或多重全局约束，就要警惕贪心可能不够。

区间调度：为什么按结束时间最早选

典型题型

单舞台节目安排
驿站班次兼容安排
会议室、活动场次、任务时间段选择

题库对应：

民族展演排期：单舞台节目场次最大化

标准策略

先按 end 升序排序。
如有需要，再按 start 和输入顺序打破并列。
维护上一次已选区间的结束时间 last_end。
当前区间若 start >= last_end，就选入答案。

为什么这个策略正确

如果你当前要在若干可选区间里选一个，结束时间最早的那个会给后面留出最大的剩余时间。换句话说，它最“不占空间”，因此最不容易妨碍后续继续选更多区间。

这不是经验，而是区间调度问题的经典最优结构。

实现骨架

items.sort(key=lambda item: (item.end, item.start, item.order))
selected = []
last_end = -1

for item in items:
    if item.start >= last_end:
        selected.append(item.name)
        last_end = item.end

额外统计量怎么顺手维护

实际题目里常常不只要“选了多少个”，还会要：

选中的名称序列
相邻已选区间的空闲总时长
最早达到某种条件的时间点

这些量通常都能在“成功选入区间”的那一刻顺手更新，不需要额外回扫一遍。

双指针配对：为什么最轻配最重

典型题型

两件物品是否能同箱
船只、车辆、箱子、座位的最少使用数
在上限约束下尽量让最重元素也被妥善安置

题库对应：

非遗巡展装箱：展品运输箱数量最少化

标准策略

先排序。
用 left 指向最轻，right 指向最重。
若 a[left] + a[right] <= limit，说明它们可以同组，两个指针一起收缩。
否则最重元素只能单独处理，right 左移。

为什么不是乱配

如果最轻的都无法和当前最重的一起放下，那么其他更重的元素更不可能和它配对，所以当前最重元素只能单独处理。这个判断一旦成立，就没有必要再尝试别的搭档。

这就是双指针贪心的核心。

实现骨架

a.sort()
left, right = 0, len(a) - 1
boxes = 0

while left <= right:
    boxes += 1
    if left == right:
        break
    if a[left] + a[right] <= limit:
        left += 1
        right -= 1
    else:
        right -= 1

贪心题里的排序不是装饰，而是算法的一部分

区间调度和双指针配对都离不开排序，因为排序之后，局部最优决策才有稳定的语义：

区间题里，“结束最早”必须建立在排序结果上。
配对题里，“最轻”和“最重”也必须建立在排序结果上。

如果排序规则错了，后面的贪心逻辑再漂亮也没有意义。

哪些题看起来像贪心，其实不是

有容量上限且组合价值不同

比如“总时长不超过 H，积分最大化”，这通常是背包 DP，不是简单贪心。

局部最优会影响后面价值结构

如果当前选一个对象会改变后续对象的收益、解锁条件或状态，单纯贪心就要谨慎。

常见错误

闭区间与半开区间混淆

区间调度题里，end == next_start 到底算不算冲突，必须先看清题面。

排序关键字不完整

题目要求并列时按 start、输入顺序或名字打破并列，如果你只按 end 排，就可能输出错序。

双指针更新顺序写错

配对成功和失败时，左右指针移动规则不同，写错一处就会多算或漏算。

只算主答案，不维护额外信息

例如本来还要输出：

成对装箱中的最大总重量
单件装箱数
已选节目列表

如果主循环里没有顺手维护，后面通常不好补。

与题库的联系

`s1-jh-08`

重点是排序后双指针最优配对。

`s4-jh-05`

重点是按结束时间排序后的区间贪心。

`s3-jh-06`

虽然主体是差分和区间合并，但同样要求你对连续活跃区间有清晰的扫描边界意识，这和区间类贪心题的“边界管理”思维是一致的。

训练建议

每写一道贪心题，先问自己一句：我这一步为什么不会后悔。
对区间题，先把 4 到 6 个区间画在数轴上，再手选一遍。
对双指针题，先手推 left 和 right 的移动过程，确保每种分支都清楚。
如果你证明不了局部决策为何正确，就不要急着把它当成贪心结论。