贪心算法模板

#include <bits/stdc++.h>
using namespace std;

// 经典：区间调度（最多选多少不重叠区间）
int maxIntervals(vector<pair<int,int>> &intervals) {
    sort(intervals.begin(), intervals.end(),
         [](auto &a, auto &b) { return a.second < b.second; });
    int count = 0, end = INT_MIN;
    for (auto &[l, r] : intervals) {
        if (l >= end) { count++; end = r; }
    }
    return count;
}

// 经典：最小硬币数（贪心仅对特定面额有效）
int minCoins(int amount) {
    int coins[] = {100, 50, 20, 10, 5, 1};
    int cnt = 0;
    for (int c : coins) {
        cnt += amount / c;
        amount %= c;
    }
    return cnt;
}

// 经典：哈夫曼编码——每次合并最小的两个
int huffman(vector<int> &freqs) {
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int f : freqs) pq.push(f);
    int cost = 0;
    while (pq.size() > 1) {
        int a = pq.top(); pq.pop();
        int b = pq.top(); pq.pop();
        cost += a + b;
        pq.push(a + b);
    }
    return cost;
}

int main() {
    vector<pair<int,int>> v = {{1,3},{2,5},{4,7},{6,9}};
    cout << maxIntervals(v) << endl;  // 2
    return 0;
}

📖 要点说明

• 贪心：每步选当前最优，不回头
• 区间调度：按右端点排序，选结束最早的
• 贪心不一定得到全局最优，需证明正确性

⚠️ 常见错误

• 区间调度按左端点排序（错误）
• 贪心解不正确但没验证
• 硬币贪心对面额有要求，不是所有面额都适用