Greedy Algorithms

Make locally optimal choices under a proof that the choices lead to a globally optimal solution.

Concept

Make locally optimal choices under a proof that the choices lead to a globally optimal solution. A greedy intuition alone is not proof.

Core problems

Activity selection, interval scheduling, meeting rooms, fractional knapsack, job sequencing, canonical coin systems, Huffman coding, minimum platforms, interval merging, and scheduling with deadlines.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

Earliest-finish-first is optimal by an exchange argument: take any optimal schedule; its first activity finishes no earlier than the greedy choice, so swapping it for the greedy choice keeps the schedule valid and the same size. Repeat on the remaining activities.

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

int main() {
    // activity selection: earliest finish time first
    vector<pair<int, int>> acts = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 9}, {5, 9}, {6, 10}, {8, 11}, {8, 12}, {2, 14}, {12, 16}};
    sort(acts.begin(), acts.end(), [](auto& a, auto& b) { return a.second < b.second; });
    int lastEnd = INT_MIN; vector<pair<int, int>> chosen;
    for (auto [s, e] : acts) if (s >= lastEnd) { chosen.push_back({s, e}); lastEnd = e; }
    cout << "activities chosen:";
    for (auto [s, e] : chosen) cout << " [" << s << "," << e << ")";
    cout << " -> " << chosen.size() << '\n';

    // minimum meeting rooms: sweep start/end events
    vector<pair<int, int>> meetings = {{0, 30}, {5, 10}, {15, 20}, {10, 15}, {25, 35}};
    vector<pair<int, int>> ev;
    for (auto [s, e] : meetings) { ev.push_back({s, +1}); ev.push_back({e, -1}); }
    sort(ev.begin(), ev.end());                               // at equal times, -1 (end) sorts before +1 (start)
    int cur = 0, rooms = 0;
    for (auto [t, d] : ev) { cur += d; rooms = max(rooms, cur); }
    cout << "meeting rooms needed: " << rooms << '\n';

    // fractional knapsack: highest value per weig
…

activities chosen: [1,4) [5,7) [8,11) [12,16) -> 4
meeting rooms needed: 2
fractional knapsack (capacity 50): 240
coins {1,3,4}, amount 6: greedy uses 3 coins (4+1+1), optimal uses 2 (3+3)

Huffman coding

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

Huffman's choice — merge the two rarest symbols — is safe because in some optimal prefix code the two rarest symbols are siblings at the deepest level (another exchange argument). The resulting code is prefix-free: no codeword is a prefix of another.

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

struct Node { long long f; char c; int l = -1, r = -1; };

int main() {
    vector<pair<char, long long>> freq = {{'a', 45}, {'b', 13}, {'c', 12}, {'d', 16}, {'e', 9}, {'f', 5}};
    vector<Node> nodes;
    using Q = pair<long long, int>;
    priority_queue<Q, vector<Q>, greater<Q>> pq;
    for (auto [c, f] : freq) { nodes.push_back({f, c}); pq.push({f, (int)nodes.size() - 1}); }
    while (pq.size() > 1) {                                     // merge the two least frequent trees
        auto [fa, a] = pq.top(); pq.pop();
        auto [fb, b] = pq.top(); pq.pop();
        nodes.push_back({fa + fb, 0, a, b});
        pq.push({fa + fb, (int)nodes.size() - 1});
    }
    map<char, string> code;
    function<void(int, string)> walk = [&](int i, string s) {
        if (nodes[i].l == -1) { code[nodes[i].c] = s.empty() ? "0" : s; return; }
        walk(nodes[i].l, s + "0"); walk(nodes[i].r, s + "1");
    };
    walk(pq.top().second, "");
    long long bits = 0, total = 0;
    for (auto [c, f] : freq) { cout << c << " (" << f << "): " << code[c] << '\n'; bits += f * (long long)code[c].size(); total += f; }
    cout << "total " << bits << " bit
…

a (45): 0
b (13): 101
c (12): 100
d (16): 111
e (9): 1101
f (5): 1100
total 224 bits for 100 characters vs 300 with a fixed 3-bit code

Graph greedy algorithms

Kruskal and Prim for minimum spanning trees; Dijkstra for non-negative edge weights.

Proof techniques

Exchange argument, cut property, staying-ahead argument, matroid intuition, and counterexample construction.

Limits

0/1 knapsack and arbitrary coin change generally do not admit the naive greedy choice. Include counterexamples.

Coins {1, 3, 4}, amount 6: greedy takes 4 + 1 + 1 (3 coins), the optimum is 3 + 3 (2 coins) — shown in the run.

0/1 knapsack, capacity 50, items (value, weight) (60,10), (100,20), (120,30): greedy by ratio takes the first two for 160; the optimum takes the last two for 220. (Fractional knapsack *is* greedy-optimal: the run shows 240 by taking two-thirds of the third item.)

Quiz

? Why is “earliest finish time first” optimal for activity selection?
+ Exchange argument: replacing an optimal schedule's first activity with the earliest-finishing one keeps it valid and the same size. :: Repeat on the rest.
- It picks the shortest activities. :: Shortest-first can fail.
- It picks the earliest start. :: Earliest start can fail badly.
- Because the input is sorted. :: Sorting enables it; the proof makes it correct.

? Coins {1, 3, 4} and amount 6. What did the run show?
+ Greedy used 3 coins, the optimum is 2. :: Non-canonical coin systems need DP.
- Greedy was optimal. :: Not here.
- No solution exists. :: 3 + 3 works.
- Both used 3 coins. :: DP found 2.

? Which problems does a greedy algorithm solve optimally? (select all that apply)
+ Fractional knapsack by value/weight :: 240 in the run.
+ Huffman coding :: Merge the two rarest.
- 0/1 knapsack by value/weight :: Counterexample: 160 vs 220.
+ Minimum spanning tree (Kruskal) :: Cut property.