The Greedy Method · Algorithms (DAA)

A greedy algorithm builds a solution step by step, always making the choice that looks best right now, and never reconsidering it. Greedy algorithms are simple and fast — but they are only correct for problems with two properties:

Greedy-choice property — a globally optimal solution can be reached by making a locally optimal choice.
Optimal substructure — an optimal solution contains optimal solutions to its subproblems.

When greedy fails

Give change for 6 using coins {1, 3, 4}. Greedy takes the largest coin first: 4 + 1 + 1 = 3 coins. But 3 + 3 = 2 coins. Greedy is wrong here — that problem needs dynamic programming. With Indian currency denominations (1, 2, 5, 10, 20, 50 …), greedy happens to be optimal.

Activity selection

Given activities with start and finish times, choose the maximum number of non-overlapping activities (one room, many meetings).

Greedy rule: sort by finish time and repeatedly pick the activity that finishes earliest among those compatible with what you already picked. Finishing early leaves the most room for the rest.

C++

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

struct Activity { char name; int start, finish; };

int main() {
    vector<Activity> acts = {{'A', 1, 4}, {'B', 3, 5}, {'C', 0, 6}, {'D', 5, 7}, {'E', 3, 9},
                             {'F', 5, 9}, {'G', 6, 10}, {'H', 8, 11}, {'I', 8, 12}, {'J', 2, 14}, {'K', 12, 16}};
    sort(acts.begin(), acts.end(), [](const Activity &a, const Activity &b) { return a.finish < b.finish; });
    int lastFinish = -1;
    cout << "Selected:";
    for (const auto &a : acts)
        if (a.start >= lastFinish) {
            cout << " " << a.name << "(" << a.start << "-" << a.finish << ")";
            lastFinish = a.finish;
        }
    cout << endl;
    return 0;
}

Output

Selected: A(1-4) D(5-7) H(8-11) K(12-16)

Try it Yourself

Time: Θ(n log n) for sorting, then Θ(n).

Fractional knapsack

A thief's knapsack holds weight W. Items have values and weights, and fractions of items may be taken (gold dust, not gold bars). Maximise value.

Greedy rule: take items in decreasing order of value per unit weight, taking a fraction of the last one if it does not fit.

C++

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

struct Item { const char *name; double value, weight; };

int main() {
    vector<Item> items = {{"silver", 60, 10}, {"gold", 100, 20}, {"silk", 120, 30}};
    double capacity = 50, total = 0;
    sort(items.begin(), items.end(), [](const Item &a, const Item &b) {
        return a.value / a.weight > b.value / b.weight;          // best ratio first
    });
    cout << fixed << setprecision(2);
    for (const auto &it : items) {
        if (capacity <= 0) break;
        double take = min(it.weight, capacity);
        total += take / it.weight * it.value;
        capacity -= take;
        cout << "take " << take << " kg of " << it.name << " (ratio " << it.value / it.weight << ")" << endl;
    }
    cout << "maximum value = " << total << endl;
    return 0;
}

Output

take 10.00 kg of silver (ratio 6.00)
take 20.00 kg of gold (ratio 5.00)
take 20.00 kg of silk (ratio 4.00)
maximum value = 240.00

Try it Yourself

Job sequencing with deadlines

Each job takes one unit of time, has a deadline and a profit earned only if finished by its deadline. Maximise total profit.

Greedy rule: consider jobs in decreasing order of profit, and schedule each in the latest free slot on or before its deadline.

C++

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

struct Job { char id; int deadline, profit; };

int main() {
    vector<Job> jobs = {{'a', 2, 100}, {'b', 1, 19}, {'c', 2, 27}, {'d', 1, 25}, {'e', 3, 15}};
    sort(jobs.begin(), jobs.end(), [](const Job &x, const Job &y) { return x.profit > y.profit; });
    int maxD = 0;
    for (auto &j : jobs) maxD = max(maxD, j.deadline);
    vector<char> slot(maxD + 1, '-');
    int profit = 0;
    for (auto &j : jobs)
        for (int t = j.deadline; t >= 1; t--)
            if (slot[t] == '-') { slot[t] = j.id; profit += j.profit; break; }
    cout << "schedule:";
    for (int t = 1; t <= maxD; t++) cout << " slot" << t << "=" << slot[t];
    cout << "\ntotal profit = " << profit << endl;
    return 0;
}

Output

schedule: slot1=c slot2=a slot3=e
total profit = 142

Try it Yourself

Greedy algorithms you will meet

Problem	Greedy rule	Lesson
Activity selection	earliest finish time	this one
Fractional knapsack	highest value/weight	this one
Job sequencing	highest profit, latest free slot	this one
Huffman coding	merge the two least frequent symbols	Huffman Coding
Minimum spanning tree	cheapest safe edge	Kruskal & Prim
Single-source shortest paths	closest unvisited vertex	Dijkstra

Test yourself

4 questions · pick an answer to check it instantly

1
In activity selection, the greedy algorithm sorts activities by...
2
For coins {1, 3, 4} and amount 6, what does greedy (largest coin first) produce?
3
Items (value, weight): (60, 10), (100, 20), (120, 30); capacity 50. What is the maximum value for fractional knapsack?
4
Which two properties make a greedy algorithm correct?

#When greedy fails

#Activity selection

#Fractional knapsack

#Job sequencing with deadlines

#Greedy algorithms you will meet

Test yourself

When greedy fails

Activity selection

Fractional knapsack

Job sequencing with deadlines

Greedy algorithms you will meet