1. 贪心直觉为什么会失灵从一次翻车经历说起1.1 一个看似简单的任务却让我连续推翻三次方案很多接触过贪心算法的人都有过类似的经历看到一个题直觉上觉得每次选当前最优的不就行了结果提交之后连样例都过不去翻车翻得莫名其妙。我印象最深的一次是刚工作不久被安排做一个会议室预订系统的排期模块。需求听起来非常简单给一批会议请求每个请求有开始时间和结束时间目标是让同一个会议室能塞下尽可能多的会议。我当时的第一反应就是经典的按结束时间排序然后逐个挑选不冲突的会议。这个思路没错跑出来的结果也确实是最优的。结果没过两天需求变了会议室不是一间而是只有有限的几间想要的是所有会议都能安排上需要的最少会议室数量是多少。我又按老思路去选结果发现只要换个数据分布之前那套最早结束优先根本不成立甚至会得到完全错误的答案。这才是真正的起点。后来我把这段时间踩的坑整理下来发现在项目里真正有用的不只是背下排序之后贪心这类套路而是先学会把问题分类这一类问题用什么策略那一类必须换策略。慢慢我形成了一套自己的拆解方式姑且叫它分类贪心。1.2 翻车之后的复盘贪心不是一种算法而是一类判断教科书里通常把贪心算法描述成每一步都采取当前看起来最优的选择希望通过一系列局部最优得到全局最优。这个定义没错但它给人的错觉是贪心就是一个固定的模板套上去就行。实际上贪心更像是一种判断逻辑它能不能用取决于你面对的问题有没有某种特殊结构。比如经典的分数背包问题可以贪心但01背包问题就不能贪心活动选择问题可以按结束时间贪心但求最小会议室数量就得换思路找零钱在某个币种体系下可以贪心换个币种体系就可能失败。也就是说同一个领域的题只要约束条件一变贪心策略就得跟着变。这给我的启发是真正值钱的是分类这一步。先判断当前问题属于哪种数学结构再决定能不能用贪心、以及该用什么贪心策略。这也是我想在这篇里完整展开的内容。2. 分类贪心的完整方法论先分域再选择后验证2.1 第一步把输入按其数学结构分类我在实际项目里做算法方案时第一件事不是动笔写代码而是先把输入数据长什么样搞清楚。这听起来很基础但绝大多数返工都出在这里。要分的关键维度有三个一是输入是离散还是连续。比如服务器资源分配CPU核数是离散的网络带宽是连续的这两类问题的贪心策略完全不同。连续问题往往可以按比例来贪心离散问题则要小心整段取舍带来的损耗。二是解空间是排列还是子集。排列类问题比如任务调度顺序、旅行路径规划通常要对顺序做贪心常用排序交换的思路子集类问题比如选哪些任务进入计划表则要对元素做取舍常用排序扫描的思路。两类问题看起来都是排序但排序的键和后续扫描方式差别很大。三是约束是否相互独立。如果约束之间互不影响贪心很容易成立如果约束会连锁触发比如选了A就必须放弃B放弃B又影响C那贪心往往要配合条件判断甚至回退机制才能继续。我在团队里经常用一张表让新人快速走这个分类流程表头就三列输入特征、常见约束、候选方向。填完这张表大约有一半的问题可以直接排除简单贪心这条路省下大量试错时间。2.2 第二步为每个类别匹配对应的贪心策略分类完成后才开始选策略。这里不是记得越多越好而是要理解每个策略成立的前提。我常用的策略其实就几张牌最小结束时间优先适用于在给定时间段内安排最多不重叠区间的问题。成立前提是每个任务的收益相同选择先结束的任务能给后面留出最多空间。最大收益优先适用于单位收益恒定、资源有限、且选择之间无后效性的问题。典型如分数背包。最小权重优先适用于需要覆盖全部点/边、且成本尽量小的图论问题比如最小生成树的Kruskal思路。最短等待优先适用于调度类问题中平均等待时间最小化的目标典型如单机短作业优先调度。每张牌背后都对应一个数学前提。如果前提不成立直接出牌就会翻车。比如最小结束时间优先在活动选择问题里是对的但换到带权重的区间调度里就是错的——因为结束时间早不代表总收益高。这也是为什么我要强调分类贪心而不是套模板贪心每一类问题要先确认它的目标函数长什么样、约束长什么样才能决定手上的牌能不能打。2.3 第三步用反例和边界条件验证选完策略后我一般不会急着提交或上线而是先构造几个反例去验证。构造反例有个省力技巧把输入缩到最小比如三个元素、两个区间、两个点。最小规模的输入能暴力枚举出所有选择直接对比贪心结果和最优结果。边界条件也是翻车高发区。我见过很多次两个任务的结束时间完全相同序列里有重复元素开始时间和结束时间刚好相等这类边角情况都会让排序或者比较逻辑出问题。做过这几步验证之后贪心方案再往代码里落出错的概率会小很多。这和我早期想清楚就开写、写完再debug的方式相比整体耗时反而少得多。3. 区间调度里的分类贪心实战从会议室到资源分配3.1 类别A求最大兼容活动数区间经典模型先看最简单也最经典的类别。你有一堆会议每个会议有个开始时间和结束时间只有一个会议室问最多能安排多少个会议。这个场景的标准解法就是按结束时间排序然后从前往后扫能安排就安排更新当前结束时间不能安排就跳过。我举个例子会议列表是[1, 3], [2, 4], [3, 5], [5, 7]按结束时间排序后就是原样收费流程开始选[1, 3]当前结束时间变成3看[2, 4]开始时间2小于当前结束时间3跳过看[3, 5]开始时间3等于当前结束时间3可以安排当前结束时间变成5看[5, 7]开始时间5等于当前结束时间5可以安排当前结束时间变成7最终安排了3个会议这是最优解。这里的关键点是按结束时间排序不是按开始时间、不是按时长。原因很直观结束得越早对后续影响越小。一个会议占用的尾巴越短后面能塞进去的越多。这个逻辑我在给新人讲的时候直接用一句话概括想让未来最宽敞就别把尾巴留太长。3.2 类别B求最小资源数量会议室数量问题同样是区间但换一个问题现在有一堆会议可能需要同时开在不同会议室问最少要几个会议室。这看起来和3.1是近亲实际解法却完全不同。这个问题的标准解法不是贪心排完就完事而是要按开始时间事件和结束时间事件一起扫描或者用最小堆维护当前占用会议室的结束时间。每来一个新会议如果最早的结束时间还早于这个新会议的开始时间就复用那个刚释放的会议室否则就新开一间。当时让我栽跟头的地方就在这里我一开始还是按最早结束优先去选会议发现无论如何都会多算房间数。原因是我把两个不同目标混在一起了。3.1的目标是单个会议室里塞最多3.2的目标是所有会议全局的最少房间数目标函数变了贪心策略也跟着变。实际项目里会议室问题还会带权重比如不同会议室容量不同、某些会议必须在大会议室等。这些扩展会让贪心失效需要转成区间图染色这类模型去处理。这也是分类的价值它让我第一时间能识别出这个扩展已经不是原来的问题类别了。3.3 类别C带权重区间调度分类后不能再用简单贪心第三个类别是给每个区间加上权重比如会议的重要程度、资源调度的利润目标变成在互不冲突的前提下选出总权重最大的区间集合。如果你试图用简单贪心几乎必然翻车。举一个最小的反例[1, 4] 权重 3 [2, 3] 权重 5 [3, 5] 权重 4按结束时间先选[2, 3]和[3, 5]这两个区间在3这一点有交叠取决于区间开闭定义我先假设两边不相交选完总权重9确实最优。但换一个例子[1, 4] 权重 6 [2, 3] 权重 5 [3, 5] 权重 4如果按结束时间排序先选[2, 3]权重5然后[3, 5]接上权重4总权重9但直接选[1, 4]权重6再选[3, 5]权重4总权重10。简单贪心给出的不是最优解。这类问题的正确方向是动态规划按结束时间排序后dp[i]表示前i个区间能得到的最大权重转移时分选第i个区间和不选第i个区间两种情况。之所以动态规划可行是因为区间有天然的线性顺序可以把问题分解成前一个不冲突的区间的最优解当前区间。这一段我想强调的就是分类贪心不等于所有问题都用贪心而是知道哪些类别该继续贪、哪些类别该及时切换算法。带权重区间调度就该切到动态规划。3.4 类别D环形区间首尾相接的额外约束还有一类在真实业务里很常见、但新手容易忽略的变种资源是循环利用的比如一周七天循环排班、环形跑道上的巡逻任务、环形仓库的拣货调度。区间首尾相接导致最后一个和第一个之间也存在约束。处理环形问题时我常用的分类手法是枚举断开点把环剪开成一条链然后在不同断开点下分别跑链式算法最后取最优。比如如果问题是不允许跨周连续工作就枚举哪一天作为起点把环形约束转化成线性约束再用之前区间贪心或动态规划的方法处理。这种处理方式不是万能的但它揭示了一个规律额外的拓扑约束往往会改变问题类别环、树、图每一种都对应不同的贪心/算法路径。所以我在做方案设计时一旦发现数据有循环结构就一定会单独分类处理绝不和普通线性区间混在一起。4. 常见分类维度与贪心策略对照四个经验框架4.1 按选择粒度分类单点选择 vs 区间选择第一个经常用到的分类维度是看每次决策选的是单独一个点还是一片连续区间。单点选择的经典例子是找零钱每次选一张面额最大的能凑就凑。区间选择的经典例子是上面说的活动安排每次选一个完整区间不能拆开。这两个类别看起来都是每次选当前最优但当前最优的定义完全不同。单点选择往往关注单个元素的贡献区间选择还额外关注对后续空间的占用。我在做资源分配时会特别提醒自己如果要分配的资源是一个整体、不可切割、而且选定之后会一直占用资源那这是一个区间选择类问题选型时候要额外考虑占用率不能只看单位贡献。4.2 按决策后效性分类路径无关 vs 路径相关第二个维度是看决策有没有后效性。所谓后效性通俗点讲就是这一步选了A会不会影响下一步的选项在经典的分数背包问题里选出一种物品往包里放不会影响其他物品可选的属性这就是路径无关。后效性最典型的反面案例是走迷宫时你走了一步之后墙壁、地形甚至剩余体力都可能改变下一步的选择空间完全取决于你之前怎么走。这个问题就是路径相关的。判断有没有后效性有个简单的测试方法把你的选择历史抹掉只把当前状态告诉另一个人问他下一步能不能做出和你一样的决策。如果光看当前状态不够、还要知道怎么走到这一步那就说明有后效性大多数单纯贪心在这里都会失效需要换成动态规划或带状态记录的搜索。4.3 按目标函数分类极值型 vs 判定型 vs 计数型第三个维度要看目标函数是求极值、做判定还是计数。求极值型最大化总价值、最小化总代价。这个最容易被贪心套路化也最容易翻车。判定型比如能不能在给定期限内完成所有任务通常转化成一个可行性检查贪心策略往往要配合排序最迟截止时间之类的技巧。计数型比如有多少种不同的方案可以完成任务这通常不能用贪心因为不同方案之间的结构关系需要完整建模往往是组合数学或动态规划的地盘。我自己的一般原则是计数型问题默认排除贪心判定型问题可以尝试先排个序再检查极值型问题则必须回到2.1和2.2的分类流程里仔细斟酌。4.4 一个我自己整理的决策清单以前我面对一个新的业务需求时经常凭直觉直接心算一下能不能贪心。后来栽过几回我整理了一个固定决策清单每次过完一遍再动手输入是离散还是连续解空间是排列、子集还是划分目标函数是极值、判定、计数还是带权重的复合决策之间互相独立吗有没有后效性有没有环形、树形、图结构这类额外拓扑约束如果贪心方案成立它的证明思路交换论证/归纳/拟阵能写出来吗前五条决定能不用贪心第六条决定为什么能用。如果第六条写不清楚我宁可先花半小时用暴力小样例验证也不直接写进生产逻辑。5. 实现细节、证明思路与隐患自查清单5.1 代码骨架把分类逻辑显式写出来前面说了这么多方法论落到代码上我最推崇的做法是没有必要一把梭把所有情况写在一起而是把分类这一步显式化成独立函数。比如在区间调度场景里我会这样划分代码结构def classify_intervals(intervals): # 返回区间问题的类别标签 has_weight any(len(interval) 2 for interval in intervals) is_cyclic check_cyclic_constraint(intervals) if not has_weight and not is_cyclic: return max_count if has_weight and not is_cyclic: return max_weight if is_cyclic: return cyclic return other def solve_max_count(intervals): # 按结束时间升序贪心 intervals.sort(keylambda x: x[1]) result [] current_end -float(inf) for i, (start, end, *_) in enumerate(intervals): if start current_end: result.append(intervals[i]) current_end end return result def solve_max_weight(intervals): # 带权重的区间调度走动态规划 intervals.sort(keylambda x: x[1]) # ... dp 逻辑省略代码结构本身不复杂但把分类逻辑单独拆分出来收益很大一是线上出问题时能快速定位是分类错了还是某个类别的求解逻辑错了二是后续加新约束时不用改动已有代码块只新增一个类别分支就行。5.2 怎么证明你的贪心是对的很多人在面试或者评审时被问为什么你的贪心是对的就卡住。我分享一个务实的办法小数据暴力验证加交换论证。小数据暴力验证很好理解就是在本地生成所有可能的解对比贪心结果。有了暴力结果兜底线上的复杂样例如果跑挂了先把输入缩小复制下来再用暴力算最优质看贪心差在哪。交换论证是更偏理论的证明方式核心思路是假设最优解跟我贪心得到的解不一样那我在不降低结果质量的前提下把最优解一步步交换成贪心解。如果每一步都能保证不劣化那就说明贪心解至少和最优解一样好。以活动选择问题为例假设最优解第一个活动不是结束时间最早的那个我可以把这个活动替换成结束时间最早的替换后剩余空间只会变大、不会缩小所以替换后仍是最优解。这个操作可以一直做下去最终说明选结束时间最早的不会丢最优解。这就是交换论证的标准姿势。5.3 容易踩的坑排序稳定性、相等元素、边界值代码层面容易踩的坑我在项目里见过很多次列几个最典型的排序键不唯一导致的非确定性问题。如果两个区间结束时间一样谁先谁后很多代码只排end不排start在某些区间开闭定义下会得到不同结果。我一般会加一个次级排序键start保证输出稳定。区间开闭定义不一致。有的场景下[1,3]和[3,5]不冲突结束和开始相接有的场景下冲突。我在实现第一行就会用注释写清楚还是以免后续维护者改错。浮点精度问题。如果区间时间是从文件或者API读进来的浮点数排序时可能会出现非常接近但不相等的值导致错误判断。我的建议是统一转成整数毫秒、微秒或者用Decimal避免精度坑。整数溢出与空输入。这个看似简单但生产环境很多出问题的代码反而是空输入、单位数输入没有单独处理。分类函数和求解函数里最好第一行就处理掉len 0和len 1的情况。5.4 一个更贴近真实业务的案例直播转码资源分配前面讲的区间调度比较理论我再用一个实践案例把整个过程串起来。假设你在做直播平台每个直播间有一路原始流需要转成多档清晰度转码要消耗CPU资源。一批直播流同时在线CPU核数有限。这个问题看起来很像最小会议室数量但其实多了一个关键约束直播流的起止时间不是固定的而是动态伸缩的而且不同档位清晰度对应不同CPU消耗。如果直接套区间扫描最小堆很可能在某些直播流延迟开始、提前结束时依然占用资源导致计算多余。分类之后我发现它其实是带权重、动态增删的区间资源分配问题不能只靠静态排序解决。最后我采用了两个层次结合的方式第一个层次按时间扫描把重叠关系算清楚第二个层次对重叠集合内部用单位资源收益排序做分配。两层思路都是贪心但每个阶段的活动目标不同这才真正把资源利用率拉了上去。这个案例让我体会很深真实业务里的问题很少是教科书原题但是它的底层结构通常是已知类别的组合。能做好分类贪心的人本质上是能识别出这个组合里头有哪些已知子问题。6. 关于贪心直觉本身的一点私人体会做了很多年开发和算法我的感受是真正难的不是学会贪心的几个套路而是在面对一个全新业务问题时能冷静判断它属于哪一类、能不能贪、该怎么贪。很多看起来应该能贪的问题只要把约束稍微改一下就变成另一类问题了同样很多看起来复杂的问题如果换成合适的排序键也能用一次排序加一轮扫描解决。我现在拿到新需求第一反应不再是这个能不能用贪心而是这个输入可以被怎样分类。分类想清楚了大部分方案都是水到渠成的事。如果你正在为某个问题反复调试、总觉得哪里差一点点却说不出来不妨退回去把输入结构、约束条件、目标函数这三件事重新梳理一遍很可能答案就已经摆在那里了。