17. Greedy Algorithms

🧸 ELI5: A greedy algorithm always grabs the best-looking option right now, without worrying about the future. Like when a cashier gives you change: for $0.67, they hand you a quarter, then a quarter, then a dime, a nickel, and 2 pennies — always picking the biggest coin that still fits, one decision at a time, never going back to reconsider.

🌍 Real life: Making change with the fewest coins (works great with US coins!). Picking the meeting room schedule that lets you attend the most meetings (always pick the meeting that ends soonest). Google Maps sometimes uses greedy-like shortcuts for quick estimates.

⚠️ Watch out: Greedy is fast but doesn't always give the perfect answer for every problem — it works great for some problems (coin change with normal coins, interval scheduling) and fails for others (coin change with weird coin values like {1, 3, 4} for target 6 — greedy might pick 4+1+1=3 coins instead of the true best, 3+3=2 coins).

📝 Pseudocode (coin change, greedy):

function greedyChange(coins, amount):
    sort coins descending
    result = []
    for coin in coins:
        while amount >= coin:
            result.add(coin)
            amount -= coin
    return result

🐹 Go:

package main

import (
	"fmt"
	"sort"
)

func greedyChange(coins []int, amount int) []int {
	sort.Sort(sort.Reverse(sort.IntSlice(coins)))
	var used []int
	for _, coin := range coins {
		for amount >= coin {
			used = append(used, coin)
			amount -= coin
		}
	}
	return used
}

func main() {
	fmt.Println(greedyChange([]int{25, 10, 5, 1}, 67))
	// [25 25 10 5 1 1] -> 67 cents using 6 coins
}

🇨 C (coins pre-sorted descending — sorting them in C means either a hand-rolled sort like #7's bubble sort or qsort from Section 11.2, so this version takes the sort as a precondition to keep the greedy logic itself front and center):

#include <stdio.h>

int greedy_change(const int *coins, int n, int amount, int *used, int used_cap) {
    int count = 0;
    for (int i = 0; i < n && count < used_cap; i++) {
        while (amount >= coins[i] && count < used_cap) {
            used[count++] = coins[i];
            amount -= coins[i];
        }
    }
    return count;
}

int main(void) {
    int coins[] = {25, 10, 5, 1}; // pre-sorted descending
    int used[16];
    int count = greedy_change(coins, 4, 67, used, 16);
    for (int i = 0; i < count; i++) printf("%d ", used[i]); // 25 25 10 5 1 1
    printf("\n");
    return 0;
}

⏱️ Complexity: Usually O(n log n) (dominated by the sort) — very fast, since it never backtracks or reconsiders.