Greedy Algorithms

Take the best choice right now

A greedy algorithm builds the answer step by step, always taking what looks best right now and never going back.

Think of it like this: Paying ₹87 with the fewest notes and coins: take the biggest that fits (₹50), then ₹20, ₹10, ₹5, ₹2.

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

vector<int> greedyCoins(int amount, const vector<int>& coinsBigFirst) {
    vector<int> used;
    for (int c : coinsBigFirst)
        while (amount >= c) { amount -= c; used.push_back(c); }
    return used;
}

int main() {
    for (int c : greedyCoins(87, {50, 20, 10, 5, 2, 1})) cout << c << ' ';
    cout << endl;
    for (int c : greedyCoins(6, {4, 3, 1})) cout << c << ' ';   // greedy is wrong here: 3 + 3 is better
    cout << endl;
    return 0;
}

Output

50 20 10 5 2 
4 1 1 

With coins 4, 3 and 1, greedy pays 6 as 4 + 1 + 1 (three coins), but 3 + 3 needs only two. Greedy only works when the “best right now” choice can never spoil the final answer.

Activity selection

Fit as many talks as possible into one room. Greedy rule: pick the talk that ends earliest:

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

int main() {
    vector<pair<int, int>> talks = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 9}, {5, 9}, {6, 10}, {8, 11}};
    sort(talks.begin(), talks.end(), [](auto& a, auto& b) { return a.second < b.second; });
    int freeAt = 0;
    for (auto [s, e] : talks)
        if (s >= freeAt) {
            cout << "(" << s << ", " << e << ") ";
            freeAt = e;
        }
    cout << endl;
    return 0;
}

Output

(1, 4) (5, 7) (8, 11) 

Remember: When greedy might fail, dynamic programming (Module 17) tries every option efficiently.