Algorithm Design Paradigms

Greedy Algorithms

At each step, take the locally best choice and never reconsider it. Greedy is fast and simple, but only correct when the problem has the right structure — it is the algorithm design paradigm most often applied incorrectly.

A greedy algorithm builds a solution incrementally, committing to the best-looking choice at each step and never backtracking
Correctness requires proof — usually via the "exchange argument": any optimal solution can be transformed into the greedy one without getting worse
Two structural properties that make greedy work: the greedy-choice property (a locally optimal choice is part of some global optimum) and optimal substructure
Classic correct greedy algorithms: Dijkstra's Shortest Paths, Prim's and Kruskal's Minimum Spanning Trees, Huffman coding, activity/interval scheduling
When greedy is wrong, it fails silently — it produces a valid answer, just not the optimal one; always verify with a counterexample or a proof, never by intuition alone

Greedy is the cheapest algorithm design paradigm to implement and the easiest to get wrong. The code is almost always short: sort by some criterion, walk through, take what fits. The hard part is entirely in the proof that the locally best choice can never be worse than deferring — which is why greedy algorithms in textbooks are always paired with a correctness argument, not just a description.

Activity selection — the canonical correct greedy

static List<Activity> selectActivities(List<Activity> activities) {
    activities.sort(Comparator.comparingInt(a -> a.finishTime));  // greedy criterion: earliest finish

    List<Activity> chosen = new ArrayList<>();
    int lastFinish = Integer.MIN_VALUE;
    for (Activity a : activities) {
        if (a.startTime >= lastFinish) {   // never conflicts with what we already chose
            chosen.add(a);
            lastFinish = a.finishTime;
        }
    }
    return chosen;
}

Sorting by finish time (not duration, not start time) is what makes this greedy choice provably optimal

Greedy criterion matters — same problem shape, different rule
Problem	Greedy rule	Correct?
Activity selection	earliest finish time first	Yes — provably optimal
Activity selection	shortest duration first	No — classic counterexample exists
Fractional knapsack	highest value/weight ratio first	Yes
0/1 knapsack	highest value/weight ratio first	No — needs Dynamic Programming
Coin change (US coins)	largest denomination first	Yes, for this coin system
Coin change (arbitrary denominations)	largest denomination first	No — needs DP