企业官网建设流程全解析

训练营刷到 Day31，贪心算法 Part05。到这个阶段，能坚持下来的人已经不是靠新鲜感，而是靠惯性。我今天不打算跟你重新背一遍贪心定义，只聊这一阶段真正该掌握的区间类贪心：它为什么难、为什么面试总爱考、以及怎样把一套方法用到三道高频题上。不管你是刚结束排序章节、正在刷贪心，还是准备在系统设计之外补算法短板，这篇内容都能直接拿来当复习提纲。区间贪心题目看着千变万化，其实核心就三件事：排序、维护边界、处理端点相等。这三件事搞明白了，你的 Part05 基本就过关了。

1. 贪心算法 Part05 到底在学什么

1.1 贪心不是猜，是一套可以验证的决策规则

很多人对贪心算法的印象是“每一步选当前最好的”，这句话没错，但太笼统。真正要命的是，你没法确定当前最好会不会坑了后面的选择。我举个经典例子：假如硬币面值是 1 元、5 元、10 元，要找 15 元，贪心先拿 10 元再拿 5 元，没问题；可如果把硬币面值换成 1 元、5 元、11 元，同样找 15 元，贪心会选择 11 + 1 + 1 + 1 + 1，一共 5 枚，但实际上 5 + 5 + 5 只需要 3 枚。这说明什么？贪心没有一个放之四海而皆准的模板，你必须在具体问题里验证“局部最优能不能推出全局最优”。如果局部最优会破坏后面的可能性，那这个题就不能用贪心硬解，可能要换动态规划。

到了训练营后期，很多同学开始浮躁，看到题目觉得“大概可以用贪心”，就直接写循环，跑过了几个用例就提交，结果被隐藏用例打回来。这种挫败感其实不是因为你笨，而是因为你没有建立一个判断框架。区间类贪心正好是理解这个框架最好的载体，因为它的每一步决策都能在数轴上画出来，验证起来非常直观。Day31 这个 Part05，与其说是在教题目，不如说是在逼你养成一个习惯：不要只看“选什么”，要看“为什么能这么选”。

1.2 区间类贪心：从“看感觉”到“画数轴”

Part05 的题目有一个共同特点：几乎全是区间题，代表就是用最少数量的箭引爆气球、无重叠区间、合并区间，加上偶尔出现的划分字母区间。这类题在 LeetCode 上的出现频率非常高，而且它们之间高度相似。你可以把每个区间理解成一天里的一段会议，目标是在同一时间只能参加一个会议的前提下，参加最多的会议。这是最经典的区间调度问题，答案就是按结束时间升序排序，然后依次挑选开始时间不早于上一个结束时间的会议。

为什么按结束时间排序，而不是按开始时间？因为结束时间早的会议不会占用后续太多时间，当前选择给未来留下的余地最大。这是区间贪心最核心的思想：做一个决策时，尽量把“负面影响”控制到最小。放到题目里，就是维护一个右边界，然后遍历排序后的区间，根据当前区间的左边界和右边界的关系做出选择。不要凭感觉猜，拿笔在草稿纸上画一条数轴，把区间都标上去。大部分区间题画完图之后，解法就已经出来了。

2. 三道必做区间题拆解：从排序到 AC

我按面试出现频率和题目之间的关联度，选了三道题：452、435、56。它们建议按这个顺序刷，因为思路是递进的。452 让你理解“选点覆盖区间”，435 让你理解“保留最多不重叠区间”，56 让你理解“合并所有重叠区间”。这三道题做完后，你对区间贪心的手感会完全不一样。

2.1 用最少数量的箭引爆气球：按右端点排序的经典套路

452 的题目背景是，平面上有一堆水平放置的气球，每个气球用一个区间[xstart, xend]表示。你可以从 x 轴上的任意点垂直向上射出一支箭，这支箭可以引爆所有横坐标覆盖该点的气球。问最少需要多少支箭。

这个问题听起来很生活化，翻译成区间语言就是：给你一堆区间，最少选多少个点，才能让每个区间都至少包含一个点。每个区间至少要被打到一次，箭的位置就是选择的点。

我的解法是先把所有区间按右端点升序排序，然后维护一个变量end，表示当前这支箭的位置。第一支箭先射在第一个气球的右端点，因为第一个气球的右端点是所有右端点里最小的，这样箭能尽可能覆盖更多的后续气球。遍历剩下的区间时，如果当前气球的左边界大于end，说明之前这支箭已经打不到它了，需要新增一支箭，同时把箭的位置更新到当前气球的右端点。否则说明它可以被当前这支箭覆盖，不需要新增。

def findMinArrowShots(points): if not points: return 0 points.sort(key=lambda p: p[1]) ans = 1 end = points[0][1] for start, stop in points[1:]: if start > end: ans += 1 end = stop return ans

这里最容易被忽略的是start > end而不是start >= end。按题目的定义，箭在坐标 x 处，只要xstart <= x <= xend，这个气球就会被引爆。所以如果前一个气球右端点是 4，当前气球左端点也是 4，那么箭射在 x = 4 时，两个气球是同时被打到的，不需要新增箭。只有当前气球的左边界严格大于当前箭的位置时才新增。

这道题的排序其实还有一个细节，当两个区间右端点相同时，谁在前面并不重要。因为我们的逻辑是拿当前区间的左边界去和上一个保留区间的右边界比较，右端点相同不会影响结果。你可以把end理解为“箭当前能覆盖到的最右侧位置”，只要后面的区间起点不超过这个位置，就都是安全的。整体时间复杂度是排序的 O(n log n)，遍历是 O(n)，空间复杂度 O(1)。

2.2 无重叠区间：一个公式解决“最少移除”

435 的题目是给一个区间集合，求最少需要移除多少个区间，才能让剩下的区间互不重叠。很多同学一看到“最少移除”就想模拟删除，其实这是把简单问题复杂化了。最少移除的数量等于区间总数减去最多能保留的区间数量。所以这个题转换成：最多能保留多少个互不重叠的区间。这就变成了我们熟悉的经典区间调度问题。

解法同样是按右端点升序排序，但是判断条件变成了start >= end。为什么是大于等于？因为两个区间如果只是端点接触，比如[1, 2]和[2, 3]，它们并没有真正“重叠”，在 435 这个题的定义里是可以同时保留的。所以当前区间的左边界只要不小于上一个被保留区间的右边界，就说明它不会造成重叠，可以留下。

def eraseOverlapIntervals(intervals): if not intervals: return 0 intervals.sort(key=lambda x: x[1]) keep = 1 end = intervals[0][1] for start, stop in intervals[1:]: if start >= end: keep += 1 end = stop return len(intervals) - keep

为什么要维护keep而不是直接维护删除数量？因为keep的含义是“能够保留的区间数”，每次遇到一个可以保留的区间，就更新右边界。最后用总数减去保留数，就是需要移除的数量。如果你在遍历过程中直接数删除次数，很容易搞混边界更新的时机。

这里我再多说一句：452 和 435 看起来很像，但边界条件完全不同。452 是>，因为端点接触时可以被同一支箭射中；435 是>=，因为端点接触不算重叠。这两道题放一起刷，就是为了让你体会到边界条件的差异有多重要。如果只背模板，遇到这种细微变化必然会错。你必须回到题目定义里去确认，端点接触到底算不算重叠。这也是为什么我反复强调画数轴的原因。

2.3 合并区间：普通区间题，却总有 30% 的人踩坑

56 合并区间是很多人觉得自己会做，但一提交就会踩坑的题。题目要求把重叠的区间合并，返回最终的区间列表。重叠的定义是[1, 4]和[4, 5]算重叠，因为两端点都包含在区间内，所以合并结果是[1, 5]。

这道题的贪心点在于：先把区间按左端点升序排序，然后从左往右扫。我们维护一个结果列表res，里面的最后一个区间代表“当前正在合并的区间”。每次遇到新区间时，看它的左边界是否大于当前合并区间的右边界。如果大于，说明它和当前合并区间没有交集，可以直接加入结果列表。如果不大于，说明重叠了，需要把当前合并区间的右边界扩展为新旧两个右边界中更大的那个。

def merge(intervals): if not intervals: return [] intervals.sort(key=lambda x: x[0]) res = [intervals[0]] for start, stop in intervals[1:]: if start > res[-1][1]: res.append([start, stop]) else: res[-1][1] = max(res[-1][1], stop) return res

这段代码有两个特别常见的坑。第一个是用start >= res[-1][1]来判断是否重叠，这样会把[1, 4]和[4, 5]拆成两个区间，不符合题意。所以这里必须用>，左边界刚好等于当前右边界时，也应该合并。第二个坑是有人会把合并逻辑写成res[-1][1] = stop，直接赋值，而不是取max。比如当前合并区间是[1, 4]，新来的区间是[2, 3]，直接赋值为 3 会导致右边界往回缩，后面的区间判断全部出错。正确做法是保留较大的右边界，也就是 4，因为合并后的区间要覆盖所有已经遇到的区间。

从思路上看，56 和 452、435 最大的区别是排序方向不同。452 和 435 按右端点排，因为我们的目标是“尽量让当前区间早点结束，给后面留出空间”；56 按左端点排，因为我们要从左往右不断扩展当前合并区间。排序方向不是随便定的，它取决于你贪心的决策变量到底是什么。

3. 排序、边界条件和贪心选择证明

3.1 到底按左端点排还是按右端点排

很多同学刷完这几道题之后会困惑：下次遇到新题，怎么知道按哪一端排序？我提供一个非常实用的判断方法：先想清楚你要维护一个什么变量，再想排序方向。

如果你是在做“选择”型贪心，比如选最多不重叠区间、用最少的点覆盖所有区间，那通常按右端点升序排序。因为右端点越小，选择它给未来留下的空间越大；当前选择对后续的“侵占”越少，就越不容易破坏全局最优。这就像安排会议时，优先参加结束早的会议，而不是开始早但拖到很晚的会议。

如果你是在做“扩展”型贪心，比如合并区间，那通常按左端点升序排序。因为合并过程中需要从左往右推进，每次取一个区间和当前结果比较，按左端点排序能保证我们不会漏掉任何一个新区间，同时可以维护当前合并区间的最大右边界。下面这个表格可以帮你快速记忆：

排序方向一旦定了，代码思路基本就定了一半。剩下的就是判断端点相等时到底用大于还是大于等于，这个完全由题目定义决定，别凭印象。

3.2 那些让人崩溃的边界条件：>、>=、还是==`

区间题的边界条件非常容易让人崩溃，因为有时候多一个等号就是错。我把这三道题的边界条件汇总成一个表，你刷完之后可以反复对照。

我见过很多人把这几道题混着背，最后写出来的代码在 435 里用了>，在 452 里用了>=，结果双双报错。我的建议是不要死记条件，而是画数轴。当两个区间的端点重合时，你只看题目问的是“能不能用一个点覆盖”，如果是，那就是>；如果问的是“算不算重叠”，一般>=；如果问的是“要不要合并”，一般也是>，因为端点重合已经算重叠了。

还有一个容易忽略的点是维护的边界变量本身。在遍历过程中，边界变量的初始值是什么？如果区间坐标可能是负数，就不要用 0 初始化，否则会把负数区间全部判错。452、435、56 这三道题里，我习惯用第一个区间初始化，这样最稳妥，也不容易出问题。

3.3 怎么说服自己“这个贪心是对的”

算法题最怕的不是写不出代码，而是写出来了但心里没底。尤其是贪心算法，你总担心某个隐藏用例会推翻你的策略。这里我分享一个我在训练营里反复用的证明方法：反证法。

拿 452 举例。我们按右端点升序排序后，第一支箭射在第一个气球的右端点。假设最优解的第一支箭没有射在这个位置，而是射在了另一个坐标 x，那么这支箭也一定在第一个气球的范围内，所以 x 一定不超过第一个气球的右端点。换句话说，我们把最优解的箭位置换成贪心选择的右端点，并不会减少它能覆盖的气球数量，因为新位置只会更靠右，覆盖范围只会更大。所以贪心选择至少和最优解一样好。这就是“贪心选择性”的证明思路。

435 的证明也类似。按右端点排序后，第一个保留的区间是所有区间里结束最早的。假设最优解没有保留这个区间，而是保留了另一个区间，那我们把这个区间换成结束最早的区间，对后续区间的选择不会造成任何阻碍，所以结果不会变差。这类证明不要求你写得多严谨，但至少要能说服自己：当前这一步选择确实不会堵死后面的路。如果你能找到一个反例说明贪心会失败，那就说明这个题不能贪心，赶紧换思路。

4. 训练营现场高频报错与排查实录

4.1 常见问题速查表

这几道题我见过太多人踩同样的坑。与其每次重新定位，不如直接对照下面的速查表排查：

每次报错不要急着在讨论区找题解，先自己拿着测试用例在纸上走一遍代码，把end的变化过程写下来。区间题的本质是维护边界，你只要把边界变化的每一步都搞清楚，代码基本不会错。

4.2 刷题心法：一道题变成一类题

训练营到了 Day31，拼的已经不是刷题数量，而是归纳能力。这三道区间题做完，我希望你能形成一个条件反射：看到“区间”“重叠”“最少”“覆盖”这些关键词，马上想到排序和维护边界。更重要的是，学会把一个题迁移到另一个题。比如划分字母字母 763，题目要求把字符串划分成尽可能多的片段，让每个字母只出现在一个片段中。本质上就是把每个字母第一次出现和最后一次出现的位置构造成一个区间，然后做合并区间的操作。你如果理解了 56，再回头看 763，会发现其实就是同一个模型换了一层外壳。

如果你们训练营的 Part05 题单里还有单调递增的数字这类题，也不用慌。它虽然不在区间模型里，但贪心的核心逻辑是一样的：找到第一个破坏单调性的位置，把前面的数字减一，后面的全部置成 9。这种题需要的是找到“必须修正的最近位置”，本质上也还是在做一个局部最优选择，然后保证后续不再变坏。所以我一直觉得，贪心 Part05 最适合的复习方式不是按顺序刷题，而是横向比较：把区间题放在一起，把数字题单独归类，然后问自己每个题背后的决策变量是什么。

最后再分享一个小技巧。每道贪心题 AC 之后，我会强迫自己写一段五十字以内的“为什么贪心是对的”，再尝试写一个如果不用贪心会错的反例。这个动作我坚持了二十道题，效果比再多刷五十道都明显。贪心算法最怕的不是不会做，而是做对了但不知道为什么，一旦题目包装换个样子，你又会觉得陌生。把这些“为什么”留在笔记里，下次遇到同类题，判断时间会短很多，信心也会稳很多。