【每日算法】Day 9-1：贪心算法精讲——区间调度与最优选择（C++实现）

掌握高效决策的核心思想！今日深入解析贪心算法的底层逻辑，聚焦区间调度与最优选择两大高频场景，结合大厂真题与严谨证明，彻底掌握“局部最优即全局最优”的算法哲学。

一、贪心算法核心思想

贪心算法（Greedy Algorithm） 是一种在每一步选择中都采取当前状态下最优决策的算法，核心特性：

1. 局部最优性：每一步选择当前最优解

2. 不可回溯性：选择后不可更改之前的决策

3. 高效性：通常时间复杂度较低

适用场景：

• 问题具有最优子结构

• 贪心策略能导致全局最优解（需数学证明）

• 常见于调度、分配、覆盖等问题

与动态规划的区别：

• 贪心：不可回退，通常更高效

• DP：保留所有可能，保证全局最优

---

二、区间调度问题

1. 无重叠区间（LeetCode 435）

问题描述：
给定多个区间，移除最少数量的区间使剩余区间互不重叠
贪心策略：

• 按结束时间排序，优先选择结束早的区间

• 每次选择与已选区间不冲突的最小区间

C++实现：

int eraseOverlapIntervals(vector<vector<int>>& intervals) {if (intervals.empty()) return 0;// 按结束时间升序排序sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) { return a[1] < b[1]; });int count = 1, end = intervals[0][1];for (int i=1; i<intervals.size(); ++i) {if (intervals[i][0] >= end) { // 不重叠count++;end = intervals[i][1];}}return intervals.size() - count;
}

2. 合并区间（LeetCode 56）

问题描述：
合并所有重叠区间
贪心策略：

按起始时间排序，依次合并重叠区间

vector<vector<int>> merge(vector<vector<int>>& intervals) {if (intervals.empty()) return {};// 按起始时间排序sort(intervals.begin(), intervals.end());vector<vector<int>> res;res.push_back(intervals[0]);for (int i=1; i<intervals.size(); ++i) {if (intervals[i][0] <= res.back()[1]) { // 重叠res.back()[1] = max(res.back()[1], intervals[i][1]);} else {res.push_back(intervals[i]);}}return res;
}

三、最优选择问题

1. 跳跃游戏（LeetCode 55）

问题描述：
数组元素表示最大跳跃长度，判断能否到达终点
贪心策略：

维护当前能到达的最远距离

bool canJump(vector<int>& nums) {int maxReach = 0;for (int i=0; i<nums.size(); ++i) {if (i > maxReach) return false; // 无法到达当前位置maxReach = max(maxReach, i + nums[i]);if (maxReach >= nums.size()-1) return true;}return true;
}

2. 分发糖果（LeetCode 135）

问题描述：
每个孩子至少1颗糖，评分高的孩子必须比相邻孩子糖多
贪心策略：

左右两次遍历，分别满足左右规则

int candy(vector<int>& ratings) {int n = ratings.size();vector<int> candies(n, 1);// 从左到右：右分高于左分则+1for (int i=1; i<n; ++i) {if (ratings[i] > ratings[i-1])candies[i] = candies[i-1] + 1;}// 从右到左：左分高于右分则取maxfor (int i=n-2; i>=0; --i) {if (ratings[i] > ratings[i+1])candies[i] = max(candies[i], candies[i+1]+1);}return accumulate(candies.begin(), candies.end(), 0);
}

四、正确性证明方法

证明方法	适用场景	示例问题
交换论证	排序类问题	区间调度
数学归纳法	递推型决策问题	跳跃游戏
剪切粘贴	存在更优解则矛盾	任务调度
贪心选择性质	证明第一步选择不影响最优解	霍夫曼编码

---

五、大厂真题实战

真题1：任务调度器（LeetCode 621）

题目描述：
给定任务列表和冷却时间n，求最短执行时间
贪心策略：

优先安排出现次数最多的任务

int leastInterval(vector<char>& tasks, int n) {vector<int> cnt(26, 0);for (char c : tasks) cnt[c-'A']++;sort(cnt.begin(), cnt.end(), greater<int>());int maxCnt = cnt[0], emptySlots = (maxCnt-1)*n;for (int i=1; i<26; ++i) {emptySlots -= min(cnt[i], maxCnt-1);}return tasks.size() + max(0, emptySlots);
}

真题2：加油站问题（LeetCode 134）

题目描述：
环形路线上找到能绕行一圈的起点
贪心策略：

• 总油量不足直接返回-1

• 局部油量不足则重置起点

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int total = 0, curr = 0, start = 0;for (int i=0; i<gas.size(); ++i) {total += gas[i] - cost[i];curr += gas[i] - cost[i];if (curr < 0) {start = i + 1;curr = 0;}}return total >= 0 ? start : -1;
}

六、常见误区与优化技巧

1. 策略错误：未严格证明贪心选择的正确性

2. 排序方式错误：区间问题未选择正确的排序键

3. 状态维护遗漏：跳跃游戏未及时更新最远距离

4. 优化技巧：

   • 预处理排序降低复杂度

   • 空间优化（如用变量替代数组）

   • 合并遍历减少循环次数

七、总结与扩展

核心优势：

• 时间复杂度通常为O(n log n)

• 代码简洁高效，适合笔试场景

• 解决资源分配问题的利器

局限性：

• 无法保证所有问题全局最优

• 需要严格的数学证明

---

LeetCode真题训练：

• 452. 用最少数量的箭引爆气球

• 406. 根据身高重建队列

• 122. 买卖股票的最佳时机 II