What is a greedy algorithm? Give examples where greedy is optimal (interval scheduling, Dijkstra, Huffman) and where it fails (coin change with arbitrary coins, 0/1 knapsack). How do you decide whether greedy is safe in a real system?

1. The two properties

• Greedy-choice property: there is an optimal solution that starts with the greedy choice.
• Optimal substructure: after making that choice, the rest is a smaller instance of the same problem.

DP needs only optimal substructure and tries all choices. Greedy bets that one choice is enough. That bet is what you must justify.

2. Exchange argument for interval scheduling

meeting  start  end
A        0      2
B        1      4
C        3      5
D        5      7
E        0      7

sorted by end: A(2), B(4), C(5), D(7), E(7)
take A        -> lastEnd = 2
B starts 1 < 2  -> skip
take C (3 >= 2) -> lastEnd = 5
take D (5 >= 5) -> lastEnd = 7
E starts 0 < 7  -> skip
result: A, C, D (3 meetings)

timeline  0   1   2   3   4   5   6   7
A         |=======|
C                     |=======|
D                             |=======|

Proof sketch: let O be any optimal schedule and let its first meeting be X. The greedy pick G ends no later than X, so replacing X with G keeps everything else valid. Repeat for the rest. So greedy is at least as good as O.

Compare the wrong rules: earliest start picks E first (0–7) and gets only 1 meeting; shortest duration can pick a short meeting that overlaps two others.

3. Why Dijkstra is greedy, and why it breaks with negative edges

      1
  S ------> A
  |         ^
 4|         | -5
  v         |
  B --------+

Dijkstra finalises A at distance 1 (closest), but S → B → A = 4 + (−5) = −1 is shorter. With only non-negative weights, any later path to A is at least as long as the current closest frontier, so finalising is safe.

4. Greedy as an approximation

Many real problems are NP-hard, so greedy is used with known bounds:

Kubernetes' scheduler scores nodes and places each pod greedily on the best-scoring node; it does not re-plan the cluster globally.

5. Canonical coin systems

Greedy change-making is optimal for the Australian set {5c, 10c, 20c, 50c, $1, $2, ...} because the system is canonical. It fails for arbitrary denominations like {1, 3, 4}. If a business lets admins configure denominations (loyalty points bundles, pack sizes), you cannot assume greedy works; use DP.

6. Testing a greedy rule

// Randomised check: greedy vs exact on small inputs
var rnd = new Random(42);
for (int trial = 0; trial < 10_000; trial++)
{
    var coins = new[] { 1 }.Concat(Enumerable.Range(0, 3).Select(_ => rnd.Next(2, 15))).Distinct().ToArray();
    int amount = rnd.Next(1, 60);
    if (GreedyCoins(coins, amount) != DpCoins(coins, amount))
    {
        Console.WriteLine($"Counterexample: coins [{string.Join(',', coins)}], amount {amount}");
        break;
    }
}

A counterexample shows up almost immediately.

7. Try it yourself

Implement interval scheduling three ways (earliest start, shortest duration, earliest end), generate 1,000 random sets of 8 meetings, and compare each with brute force over all subsets. Only earliest end matches brute force every time.

public sealed record Meeting(string Name, TimeOnly Start, TimeOnly End);

// Interval scheduling: max non-overlapping meetings. O(n log n), optimal.
public static List<Meeting> MaxMeetings(IEnumerable<Meeting> meetings)
{
    var chosen = new List<Meeting>();
    TimeOnly lastEnd = TimeOnly.MinValue;
    foreach (var m in meetings.OrderBy(m => m.End))     // greedy rule: earliest end
        if (m.Start >= lastEnd)
        {
            chosen.Add(m);
            lastEnd = m.End;
        }
    return chosen;
}

// Greedy load balancing (LPT): longest job first to least-loaded worker. Heuristic, <= 4/3 optimal.
public static Dictionary<int, List<Job>> Assign(IEnumerable<Job> jobs, int workers)
{
    var load = new PriorityQueue<int, TimeSpan>();          // worker id by total assigned time
    var result = new Dictionary<int, List<Job>>();
    for (int w = 0; w < workers; w++) { load.Enqueue(w, TimeSpan.Zero); result[w] = new(); }

    foreach (var job in jobs.OrderByDescending(j => j.EstimatedDuration))
    {
        load.TryDequeue(out var worker, out var current);
        result[worker].Add(job);
        load.Enqueue(worker, current + job.EstimatedDuration);
    }
    return result;
}

public sealed record Job(string Id, TimeSpan EstimatedDuration);

// Greedy change: only correct for canonical coin systems
public static int GreedyCoins(int[] coins, int amount)
{
    int count = 0;
    foreach (var c in coins.OrderDescending())
    {
        count += amount / c;
        amount %= c;
    }
    return amount == 0 ? count : -1;
}