Greedy Algorithms

A greedy algorithm builds a solution step by step, always choosing the best option right now, without worrying about future consequences.

It’s like always picking the biggest cookie first — hoping it leads to the best total outcome.

What does greedy mean?

“Greedy” means locally optimal — at each step, you take the choice that looks best at that moment.

Sometimes this also gives the global optimum (the overall best answer), but not always. The trick is knowing when greediness actually works.

Common idea

You have a goal (like minimizing cost or maximizing value).
You make a choice that seems best right now.
You repeat until the job is done.

You never go back or change previous decisions.

Example pattern:

while (problem not solved) {
    pick the best possible option right now;
    update the state;
}

Example problems

Coin change

You have coins of 1, 5, 10, and 25. Find the minimum number of coins to make 63.

Solution

Greedy idea: always take the largest coin possible.

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

int main() {
    int amount = 63;
    vector<int> coins = {25, 10, 5, 1};
    int count = 0;

    for (int c : coins) {
        count += amount / c;
        amount %= c;
    }
    cout << count; // 6 coins
}

It picks: 25 + 25 + 10 + 1 + 1 + 1 = 63 → 6 coins.
This greedy strategy works for most real coin systems.

Activity selection

You are given activities with start and end times. You can only do one at a time. What is the maximum number of activities you can complete?

Solution

Greedy idea: always pick the activity that finishes first.

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

int main() {
    vector<pair<int, int>> act = {{1, 3}, {2, 5}, {4, 6}, {6, 8}, {5, 7}};
    sort(act.begin(), act.end(), [](auto &a, auto &b){ return a.second < b.second; });

    int count = 0, end = 0;
    for (auto &p : act) {
        if (p.first >= end) {
            count++;
            end = p.second;
        }
    }
    cout << count; // 3
}

We always take the next available activity that ends earliest — leaving more time for the rest.

When greedy works

Greedy algorithms work when local choices lead to the global best answer.
This happens if the problem has the greedy choice property and optimal substructure.

You don’t need to memorize these terms — just test if greedy logic always works for all cases.

Examples that work

Coin change (1, 2, 5 coins) — picking largest coin first always gives fewest coins.
Shortest tasks first — doing small jobs early fits more into limited time.
Maximize sum with limit — picking largest positive numbers first.

Examples that fail

Coin change with coins {1, 3, 4}, amount = 6
- Greedy picks 4 + 1 + 1 = 3 coins, but best is 3 + 3 = 2 coins.
- So greedy fails here — picking the biggest first wasn’t globally best
Packing items by size — taking the biggest item first might block space for smaller ones that would fit better together.

Greedy steps checklist

Sort something (by value, end time, ratio, etc.)
Loop through it
Pick the best valid choice each time
Update state (remaining capacity, time, etc.)

sort(items.begin(), items.end(), rule);
for (auto &item : items) {
    if (can_take(item)) take(item);
}

Advantages

Very simple and fast
Usually O(n log n) or better
Often works surprisingly well
Easy to reason about

Disadvantages

Doesn’t always give the correct (optimal) result
Can fail if future choices depend on earlier ones
Must prove or test correctness carefully

Tips

Always check if a greedy choice can cause future problems
Try building counterexamples to test if it’s safe
Many problems combine greedy + sorting

Quick summary

Greedy = choose the best local option at each step
Works when local choices guarantee a global optimum
Common in scheduling, graphs, and resource allocation
Usually very fast and simple to code