贪心算法基础

例题1：区间选点问题（Interval Point Selection）

难度：★☆☆☆☆ 频率：高

题目描述： 给定 n 个闭区间 [a_i, b_i]，在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点（右端点也算区间内）。

贪心策略： 将所有区间按右端点从小到大排序，选择第一个未覆盖的区间的右端点。

#include <vector>
#include <algorithm>
using namespace std;

struct Interval {
    int left, right;
};

// 贪心选点：按右端点排序
int selectPoints(vector<Interval>& intervals) {
    if (intervals.empty()) return 0;

    // 按右端点升序排序
    sort(intervals.begin(), intervals.end(),
         [](const Interval& a, const Interval& b) {
             return a.right < b.right;
         });

    int count = 1;                 // 至少需要一个点
    int currentPoint = intervals[0].right;  // 选第一个区间的右端点

    for (int i = 1; i < intervals.size(); i++) {
        // 如果当前区间不包含已选的点
        if (intervals[i].left > currentPoint) {
            count++;
            currentPoint = intervals[i].right;  // 选新区间的右端点
        }
    }
    return count;
}

复杂度分析： O(n log n) -- 排序 O(n log n)，扫描 O(n)。

正确性证明： 设贪心选择的第一个点为第一个区间的右端点。对于任意一个不包含该点的区间，该区间的左端点必然大于第一个区间的右端点，因此必须另选新的点。按此方式递归处理，每个点都尽可能多地覆盖区间，因此总的选点数量最小。

例题2：区间覆盖问题（Interval Coverage）

难度：★★☆☆☆ 频率：高

题目描述： 给定一个目标区间 [S, T] 和 n 个小区间 [a_i, b_i]，选择尽量少的小区间来覆盖目标区间。

贪心策略： 将所有区间按左端点从小到大排序，每次选择能覆盖当前起点且右端点最远的区间。

#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

struct Interval {
    int left, right;
};

int minCoverage(vector<Interval> intervals, int S, int T) {
    // 按左端点升序排序
    sort(intervals.begin(), intervals.end(),
         [](const Interval& a, const Interval& b) {
             return a.left < b.left;
         });

    int count = 0;
    int curEnd = S;        // 当前已覆盖的右端点
    int i = 0;
    int n = intervals.size();

    while (curEnd < T) {
        int farthest = curEnd;

        // 在所有左端点 ≤ curEnd 的区间中，找右端点最大的
        while (i < n && intervals[i].left <= curEnd) {
            farthest = max(farthest, intervals[i].right);
            i++;
        }

        // 无法继续覆盖
        if (farthest == curEnd) return -1;

        count++;
        curEnd = farthest;  // 更新当前覆盖位置
    }
    return count;
}

复杂度分析： O(n log n) -- 排序 O(n log n)，每个区间最多被访问一次 O(n)。

例题3：最大不相交区间数量

难度：★★☆☆☆ 频率：高

题目描述： 给定 n 个区间，选择尽量多的区间，使得这些区间两两不相交（端点重合也算相交）。

贪心策略： 按右端点从小到大排序，优先选择右端点最小的区间。

#include <vector>
#include <algorithm>
using namespace std;

struct Interval {
    int left, right;
};

int maxNonOverlapping(vector<Interval> intervals) {
    if (intervals.empty()) return 0;

    // 按右端点升序排序
    sort(intervals.begin(), intervals.end(),
         [](const Interval& a, const Interval& b) {
             return a.right < b.right;
         });

    int count = 1;
    int lastRight = intervals[0].right;

    for (int i = 1; i < intervals.size(); i++) {
        // 如果当前区间左端点 ≥ 上一个选中区间的右端点（不相交）
        if (intervals[i].left >= lastRight) {
            count++;
            lastRight = intervals[i].right;
        }
    }
    return count;
}

注意： 本题与"区间选点"问题具有对偶性。实际上，最大不相交区间数量等于最少选点数。

例题4：加油站问题（Gas Station）

难度：★★★☆☆ 频率：中

题目描述： 一个环形路线上有 n 个加油站，第 i 个加油站有汽油 gas[i]，从 i 到 i+1 需要消耗汽油 cost[i]。求是否存在一个起点，使得汽车能绕行一周。

贪心策略： 如果一个位置开始无法到达下一个加油站，则这个位置和中间经过的所有位置都不能作为起点。

#include <vector>
using namespace std;

int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
    int n = gas.size();
    int totalTank = 0;   // 总油量盈余
    int curTank = 0;     // 当前油量
    int start = 0;       // 起点

    for (int i = 0; i < n; i++) {
        int diff = gas[i] - cost[i];
        totalTank += diff;
        curTank += diff;

        // 当前起点无法到达 i+1
        if (curTank < 0) {
            // 从 i+1 重新开始尝试
            start = i + 1;
            curTank = 0;
        }
    }

    // 总油量 ≥ 总消耗，则一定能找到起点
    return totalTank >= 0 ? start : -1;
}

正确性分析： 关键性质 -- 如果从起点 start 出发到 i 时油量变为负，则起点 start 到 i 之间的任何节点都不能作为起点。这是因为从 start 出发到中间节点 k 时油量非负，所以从 start 到 k 积累的油量是正的，而从 k 出发等于在正油量基础上出发都到不了 i，直接从 k 出发更不可能。

例题5：柠檬水找零（Lemonade Change）

难度：★☆☆☆☆ 频率：中

题目描述： 每杯柠檬水售价 5 美元，顾客排队购买，每位顾客只买一杯，支付 5、10 或 20 美元。初始没有零钱，判断能否给每位顾客正确找零。

贪心策略： 收到 20 美元时，优先用 10+5 找零（因为 5 美元更通用），其次用 5+5+5。

#include <vector>
using namespace std;

bool lemonadeChange(vector<int>& bills) {
    int five = 0, ten = 0;  // 分别记录 5 元和 10 元的数量

    for (int bill : bills) {
        if (bill == 5) {
            five++;
        } else if (bill == 10) {
            if (five == 0) return false;
            five--;
            ten++;
        } else {  // bill == 20
            // 贪心：优先用 10+5 组合找零
            if (ten > 0 && five > 0) {
                ten--;
                five--;
            } else if (five >= 3) {
                five -= 3;
            } else {
                return false;
            }
        }
    }
    return true;
}

/*
 * 为什么收到20时要优先用10元？
 * 因为5元在找零中扮演更关键的角色：
 * - 5元可以给10元和20元找零
 * - 10元只能给20元找零
 * 保留5元能应对更多找零场景，所以20元尽量先用10元找零。
 */

复杂度分析： O(n) -- 一次线性扫描即可。

例题6：分发饼干（Assign Cookies）

难度：★☆☆☆☆ 频率：中

题目描述： 每个孩子有一个胃口因子 g[i]，每块饼干有大小 s[j]。当饼干大小 ≥ 孩子胃口时，孩子会满足。每个孩子最多给一块饼干，求最多能满足多少个孩子。

贪心策略： 将孩子胃口和饼干大小排序，用最小的饼干去满足胃口最小的孩子（每次给最接近胃口大小的饼干）。

#include <vector>
#include <algorithm>
using namespace std;

int findContentChildren(vector<int>& g, vector<int>& s) {
    sort(g.begin(), g.end());   // 孩子胃口升序
    sort(s.begin(), s.end());   // 饼干大小升序

    int child = 0;  // 已满足的孩子数量
    int cookie = 0; // 当前考虑的饼干索引

    while (child < g.size() && cookie < s.size()) {
        if (s[cookie] >= g[child]) {
            child++;  // 该孩子得到满足
        }
        cookie++;  // 无论是否满足，当前饼干都被消耗
    }
    return child;
}

/*
 * 为什么贪心策略有效？
 * 对于胃口最小的孩子，用最小的可用饼干去满足，保留了更大的饼干。
 * 这样做不会影响更多孩子被满足的总数。证明：
 * 假设最优解中胃口最小的孩子用了更大的饼干，将其替换为最小的可用饼干后，
 * 更大的饼干可以留给胃口更大的孩子，总满足数不会减少。
 */

复杂度分析： O(n log n + m log m) -- 两次排序，一次线性扫描。

LeetCode 经典贪心题目（按难度排序）

• 简单： 455. 分发饼干 | 860. 柠檬水找零 | 122. 买卖股票的最佳时机 II | 392. 判断子序列
• 中等： 55. 跳跃游戏 | 45. 跳跃游戏 II | 134. 加油站 | 406. 根据身高重建队列 | 435. 无重叠区间 | 452. 用最少数量的箭引爆气球
• 困难： 135. 分发糖果 | 502. IPO | 630. 课程表 III | 757. 设置交集大小至少为2