面试牛牛如何掌握贪心算法与区间问题面试题
贪心算法是各级别技术面试的常客。从初级工程师的编程筛选到资深工程师的深度考核，面试官都会用贪心问题来检验你能否识别局部最优选择并将其推广到全局最优解。难点往往不在代码本身，而在于识别贪心策略的适用性并证明其正确性。借助 AI 面试助手 强化你的模式识别能力，你可以在任何编程面试中自信地捕捉到贪心信号。
为什么贪心算法在面试中如此常见
贪心算法看似简单，实则暗藏玄机。代码通常很简短，但背后的正确性推理才是区分强弱候选人的关键。面试官青睐贪心问题，因为它同时考察三个维度：模式识别（贪心是否适用？）、证明直觉（为什么局部选择能导向全局最优？）以及边界情况意识（多个元素相等或输入为空时怎么办？）。
与动态规划探索所有子问题不同，贪心算法在每一步做出一个选择后就不再回头。这使得贪心解法效率极高——通常由于排序而达到 O(n log n)——但也很脆弱。一个适用于某变体的贪心策略可能在稍作修改后完全失效。这种简洁与正确性之间的张力，正是这类题目成为面试利器的原因。
贪心何时有效？
在深入具体模式之前，你需要一个判断贪心是否适用的思维框架。以下两个性质必须同时满足：
贪心选择性质
通过在每一步做出局部最优选择，可以得到全局最优解。你无需重新考虑已做出的决定。
最优子结构
做出贪心选择后，剩余的子问题与原问题具有相同的结构。子问题的最优解加上贪心选择，就构成了原问题的最优解。
如果两个性质都满足，贪心有效。如果任一性质缺失，你可能需要动态规划或其他技术。面试中，快速验证的方法是尝试构造一个反例。如果几次尝试后找不到反例，贪心大概率是安全的。
六大核心贪心模式
模式一：区间调度与活动选择
这是最经典的贪心模式。给定一组区间（活动、会议、任务），选择最大数量的互不重叠的区间。
核心洞察：按结束时间排序，然后贪心地选择不与前一个已选区间重叠的最早结束的区间。
为什么按结束时间排序而不是开始时间？因为选择最早结束的区间为后续区间留出了最大空间。按开始时间排序可能导致你选中一个很长的区间，从而阻塞许多较短的区间。
时间复杂度：排序 O(n log n)，贪心扫描 O(n)。
常见变体：
- 一个人最多能参加多少个不重叠的会议
- 所需的最少会议室数量（此变体使用不同技巧——见模式二）
- 射爆重叠气球所需的最少箭数
模式二：合并区间
给定一组区间，合并所有重叠区间并返回不重叠的区间列表。
解题方法：按开始时间排序。用第一个区间初始化结果。对于后续每个区间，检查它是否与结果中最后一个区间重叠（即其开始时间小于等于前一个的结束时间）。如果重叠，将前一个的结束时间扩展为两者的最大值。如果不重叠，将新区间加入结果。
为什么有效：按开始时间排序保证了如果区间 B 与区间 A 重叠，B 会紧跟在 A 之后出现（或在同一合并组中）。排序后出现的任何区间如果不与 B 重叠，也不可能与 A 重叠。
时间复杂度：排序 O(n log n)，合并扫描 O(n)。
常见变体：
- 将新区间插入到已排序的不重叠区间列表中
- 求最少会议室数（使用最小堆跟踪结束时间，或扫描线 +1/-1 事件法）
- 判断一个人是否能参加所有会议（排序后检查是否有重叠即可）
模式三：跳跃游戏与可达性
给定一个数组，每个元素代表从该位置可以跳跃的最大长度，判断是否能到达最后一个下标（或求最少跳跃次数）。
可达性的贪心洞察：维护变量 maxReach 跟踪当前能到达的最远下标。遍历数组：在每个下标 i 处，更新 maxReach = max(maxReach, i + nums[i])。如果在某个点 i > maxReach，则无法继续。如果 maxReach 达到或超过最后一个下标，返回 true。
最少跳跃的贪心洞察：使用类 BFS 的层次扩展。跟踪当前层的最远到达距离和下一层的最远到达距离。每次耗尽当前层时，增加跳跃计数并进入下一层。
时间复杂度：两个变体均为 O(n)——无需排序。
常见变体：
- 跳跃游戏 I（能否到达终点？）
- 跳跃游戏 II（到达终点的最少跳跃次数）
- 视频拼接（覆盖时间范围的最少片段数）
模式四：带冷却时间的任务调度
给定任务列表和冷却周期 n，求执行所有任务所需的最少时间单位。相同任务的连续执行之间必须至少有 n 个冷却单位。
贪心洞察：频率最高的任务决定了整个调度。统计任务频率。频率最高的任务（频率为 f）在其执行之间创建 (f - 1) 个大小为 n 的间隔。按频率顺序用其他任务填充这些间隔。如果没有足够的不同任务来填满间隔，则会产生空闲时间。
公式：result = max(总任务数, (maxFreq - 1) * (n + 1) + 最高频率任务的个数)。
为什么这个公式有效？第一项处理有足够任务填满所有间隔的情况。第二项处理因一个或多个任务频率占主导地位而不可避免出现空闲的情况。
时间复杂度：O(n)，其中 n 为任务数量（对 26 个大写字母做计数排序）。
模式五：分数背包与贪心选择
给定具有重量和价值的物品以及一个有承重限制的背包，最大化总价值。与 0/1 背包（需要 DP）不同，分数变体允许取物品的一部分。
贪心洞察：按价值与重量的比率降序排序。贪心地尽可能多取比率最高的物品，然后移向下一个。
为什么贪心在这里有效但对 0/1 背包无效？因为分数物品可以分割，所以选择最佳比率的贪心决策永远不会"浪费"容量。而在 0/1 背包中，取一个高比率物品可能消耗过多重量，排除了总价值更大的小物品组合。
时间复杂度：排序 O(n log n)。
常见变体：
- 分配饼干给孩子（对贪心因子和饼干尺寸都排序）
- 救生艇（排序后双指针）
- 划分字母区间（贪心区间合并变体）
模式六：哈夫曼编码与贪心构造
通过反复合并两个最低频率的节点来构建最优前缀无冲突编码树。此模式在编程面试中出现较少，但在数据压缩相关的系统设计讨论中很常见。
贪心洞察：先合并两个频率最低的符号，确保它们获得最长的编码，从而最小化总编码长度。
时间复杂度：使用最小堆 O(n log n)。
面试中的出现场景：设计压缩系统的问题、最优合并模式（以最小总 I/O 合并 K 个排序文件），有时也作为直接编码题。
如何在面试中证明贪心的正确性
面试官经常在你给出贪心解法后追问"你怎么知道这是最优的？“你不需要严格的数学证明，但应该有一个结构化的论证：
交换论证：假设存在一个与贪心解不同的最优解。证明你可以将最优解中的一个元素替换为贪心选择，且不会使解变差。重复此交换直到最优解与贪心解一致。
保持领先论证：证明在每一步之后，贪心解至少与任何其他解一样好。如果贪心在每一步都保持领先，那么它在最终结果上也必然领先。
在实际面试中，一句清晰的话如"按结束时间排序确保我们总是为未来的区间留出最大空间，所以任何其他选择只能等于或更差"就足以应对大多数场景。借助 OfferBull 反复演练这些论证，直到它们变得自然流畅。
常见错误及如何避免
错误一：在需要 DP 时使用贪心
经典陷阱：0/1 背包看起来与分数背包相似，但贪心会失败。始终问自己"能否构造一个反例，证明贪心选择导致次优结果？“如果找到了，就切换到 DP。
错误二：按错误的键排序
在区间调度中，按开始时间而非结束时间排序会得到错误答案。在任务调度中，按截止时间而非频率排序会导致次优调度。排序键是贪心策略的核心——搞错它，一切都会崩塌。
错误三：忽略边界情况
空输入、单元素输入、所有区间重叠、所有区间互不相交、重复值——这些边界情况会绊倒即使是经验丰富的候选人。在宣布解法完成之前，至少走查两个边界情况。
错误四：未阐述贪心直觉
很多候选人直接跳到代码而不解释为什么贪心有效。这是一个错失的机会。正确性论证往往比实现代码更重要，因为它展示了理解的深度。
练习路线图
如果你正在准备面试并希望建立贪心算法的熟练度，请按以下路线推进：
第一周：基础 — 解决活动选择、合并区间和会议室问题。重点理解每个问题的排序键和正确性证明。
第二周：数组贪心 — 攻克跳跃游戏变体、加油站（环形路线）和分糖果问题。这些题目训练你跟踪运行状态变量的能力。
第三周：进阶模式 — 练习任务调度器、划分字母区间和重组字符串。这些问题结合了频率统计与贪心放置。
第四周：综合练习 — 在不知道类别的情况下做题。真正的面试不会标注问题是"贪心"类型。你的任务是识别信号。使用 AI 面试工具 进行模拟面试可以显著加速这种识别过程。
贪心 vs. 动态规划：快速决策框架
当你遇到一个新的优化问题时，按以下清单检查：
- 能否为贪心找到反例？ 如果能，使用 DP。
- 问题是否有重叠子问题？ 如果有，使用 DP。
- 能否排序后一次遍历解决？ 如果能，贪心大概率正确。
- 允许取分数是否让问题变简单？ 如果分数版本容易但整体版本困难，整体版本很可能需要 DP。
这个框架无法覆盖所有情况，但能处理绝大多数面试问题。通过限时模拟面试练习是将这些决策点内化为第二本能的最佳方式。
总结
贪心算法奖励清晰的思维。代码几乎总是很短——通常不超过 20 行——但推理必须严密。在你的下一次面试中，克制直接写代码的冲动。花前两分钟阐述排序键、贪心选择和简要的正确性论证。这种结构化的方法向面试官传达出你像资深工程师一样思考，而不仅仅是一个写代码的人。
掌握你的职业发展路径：
- 官方网站： www.offerbull.net
- iOS 应用： iPhone/iPad 下载
- Android 应用： Android 下载