Lesson 2 · Problem-solving methods

Greedy Algorithms

A greedy algorithm builds a solution piece by piece, always choosing the next piece that offers the most immediate benefit. While it doesn't work for all problems, when it does, it is usually the fastest and simplest approach.

The Greedy Choice Property

This property states that a globally optimal solution can be arrived at by selecting a local optimum. If you want the fewest coins to make change for $0.99 using standard US currency, you greedily pick the largest coin possible at each step.

However, if your coin system was $0.25, $0.20, and $0.01, and you needed $0.40, a greedy approach would pick $0.25, $0.01x15 (16 coins), while the optimal is $0.20x2 (2 coins).

Must prove safety of the greedy choice
Counterexamples prove it wrong
Usually involves sorting the input first

Activity Selection

A classic greedy problem: given a set of activities with start and end times, find the maximum number of non-overlapping activities you can perform.

The optimal greedy strategy is to always pick the available activity that ends the earliest, leaving as much time as possible for subsequent activities.

Sort by end time
Iterate and pick non-overlapping
O(N log N) time due to sorting

Key reference

Terms, operations, and practical uses

Core vocabulary

Greedy ChoiceMaking the choice that looks best at the current moment without considering the long-term consequences.
Local OptimumThe best possible choice at a specific step in the algorithm.
Global OptimumThe absolute best possible solution for the entire problem.

Characteristics

IrrevocableGreedy algorithms typically never undo or reconsider a choice once it is made (no backtracking).
Proof of CorrectnessA mathematical proof is usually required to show that local greedy choices indeed lead to the global optimal solution.
Sorting PrerequisiteMost greedy algorithms require sorting the input data first, making their time complexity bounded by O(N log N).

Classic problems

Activity SelectionChoosing the maximum number of non-overlapping intervals (activities) by sorting by end time.
Huffman CodingCreating an optimal prefix code for data compression by repeatedly merging the least frequent items.
Fractional KnapsackUnlike 0/1 Knapsack, taking fractions of items allows a greedy approach based on value/weight ratio.

Code example

Make change for 40 cents using US coins

def make_change(amount, coins):
    count = 0
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
    return count
print(make_change(40, [25, 10, 5, 1]), 'coins (25, 10, 5)')

int makeChange(int amount, vector<int>& coins) {
    int count = 0;
    for (int coin : coins) {
        while (amount >= coin) {
            amount -= coin;
            count++;
        }
    }
    return count;
}

static int makeChange(int amount, int[] coins) {
    int count = 0;
    for (int coin : coins) {
        while (amount >= coin) {
            amount -= coin;
            count++;
        }
    }
    return count;
}

Inputamount = 40, coins = [25, 10, 5, 1]

Output3 coins (25, 10, 5)

Example

Run the example step by step

Output

Huffman Coding

Greedy algorithms are used in data compression. Huffman coding builds a tree to assign shorter binary codes to more frequent characters.

At every step, it greedily merges the two least frequent characters/nodes into a new node until a single tree remains.

Used in ZIP and JPEG compression
Optimal prefix code
Uses a priority queue (min-heap)

When Greedy Fails

Greedy algorithms fail when a locally optimal choice locks you out of a globally optimal path. The Knapsack Problem is a prime example: you cannot greedily pick items by value-to-weight ratio if you cannot take fractions of items.

When greedy fails, you typically fall back to Dynamic Programming or Backtracking to evaluate multiple paths.

Fails on 0/1 Knapsack
Fails on finding longest paths
Fails when future consequences matter