Greedy Algorithms

From reach to choice

In Graph Algorithms, you practiced exploring what is reachable. In Dynamic Programming, you learned to reuse overlapping subproblem results.

Now we study a different mindset: make the best next choice, commit to it, and move forward.

That is the heart of a greedy algorithm.

Greedy algorithms matter because they are often:

• simple to implement
• fast in practice
• common in interviews and production code
• easy to get subtly wrong

The key skill is not just writing the loop. It is knowing when the greedy choice is actually safe.

The greedy promise

A greedy algorithm repeatedly chooses the option that looks best right now according to a rule.

while there is still work to do:
    choose the best available option
    commit to it
    update the remaining problem

The danger is obvious: the best local choice might block a better global result.

So a greedy algorithm needs more than confidence. It needs a reason that the local choice is safe.

Two signals help:

• Greedy-choice property: a locally best choice can be part of a globally optimal solution.
• Optimal substructure: after making that choice, the remaining problem is the same kind of problem.

You saw optimal substructure in Dynamic Programming. Greedy goes further: it asks whether we can avoid trying all choices.

You want to schedule the maximum number of non-overlapping activities. Each activity has a start time and an end time.

Which greedy rule is the classic safe choice?

A classic greedy win

Suppose you are choosing the largest set of non-overlapping activities.

The greedy rule is:

Sort by finish time, then repeatedly take the first activity that starts after the last selected one ends.

This builds on Sorting and Searching Algorithms: the sort creates the order that makes the greedy choice meaningful.

The invariant is simple:

• selected activities never overlap
• among all choices so far, we have left the most future room possible

```csharp
using System;
using System.Collections.Generic;
using System.Linq;

public class Activity
{
    public string Name;
    public int Start;
    public int End;

    public Activity(string name, int start, int end)
    {
        Name = name;
        Start = start;
        End = end;
    }
}

public class Program
{
    public static void Main()
    {
        var activities = new List<Activity>
        {
            new Activity("A", 0, 6),
            new Activity("B", 1, 4),
            new Activity("C", 3, 5),
            new Activity("D", 5, 7),
            new Activity("E", 3, 9),
            new Activity("F", 6, 10),
            new Activity("G", 8, 12),
            new Activity("H", 8, 11)
        };

        var selected = new List<Activity>();
        int lastEnd = int.MinValue;

        foreach (var activity in activities.OrderBy(a => a.End))
        {
            if (activity.Start >= lastEnd)
            {
                selected.Add(activity);
                lastEnd = activity.End;
            }
        }

        Console.WriteLine("Selected activities:");
        foreach (var activity in selected)
        {
            Console.WriteLine($"{activity.Name}: {activity.Start}-{activity.End}");
        }

        Console.WriteLine($"Total selected = {selected.Count}");
    }
}
```

The exchange argument

Greedy proofs often use an exchange argument.

For interval scheduling, imagine an optimal schedule. Let its first activity be X.

Now compare X with the activity G chosen by the greedy rule: the one that finishes earliest.

Because G finishes no later than X, replacing X with G cannot make the rest of the schedule worse.

Optimal:  [ X ][ ...remaining compatible activities... ]
Greedy:   [ G ][ ...same remaining activities still fit... ]

So there exists an optimal solution that starts with the greedy choice. After that, the remaining problem has the same structure.

That is exactly the kind of reasoning that separates correct greedy algorithms from hopeful guessing.

True or false: if a problem has optimal substructure, then a greedy algorithm is guaranteed to find the optimal answer.

Local best can be a trap

A common example is coin change.

For U.S.-style coins, repeatedly taking the largest coin often works. But not every coin system behaves that way.

With coins {1, 3, 4} and amount 6, greedy picks:

4 + 1 + 1 = 3 coins

But the optimal answer is:

3 + 3 = 2 coins

This is why the algorithmic thinking checklist still matters: trace, compare, and look for a proof.

```csharp
using System;
using System.Linq;

public class Program
{
    public static void Main()
    {
        int[] coins = { 1, 3, 4 };
        int amount = 6;

        int greedyCount = GreedyCoinCount(coins, amount);
        int optimalCount = OptimalCoinCount(coins, amount);

        Console.WriteLine($"Coins: {string.Join(", ", coins)}");
        Console.WriteLine($"Amount: {amount}");
        Console.WriteLine($"Greedy coin count: {greedyCount}");
        Console.WriteLine($"Optimal coin count: {optimalCount}");
    }

    static int GreedyCoinCount(int[] coins, int amount)
    {
        int count = 0;

        foreach (int coin in coins.OrderByDescending(c => c))
        {
            while (amount >= coin)
            {
                amount -= coin;
                count++;
            }
        }

        return amount == 0 ? count : int.MaxValue;
    }

    static int OptimalCoinCount(int[] coins, int amount)
    {
        int[] dp = new int[amount + 1];
        Array.Fill(dp, amount + 1);
        dp[0] = 0;

        for (int current = 1; current <= amount; current++)
        {
            foreach (int coin in coins)
            {
                if (current >= coin)
                {
                    dp[current] = Math.Min(dp[current], dp[current - coin] + 1);
                }
            }
        }

        return dp[amount];
    }
}
```

Fill in the blank:

The property that says a locally best choice can be part of a globally optimal solution is called the ______.

How to design greedily

Use this checklist before trusting a greedy solution:

1. Define the objective
   What are you maximizing or minimizing?

2. List candidate choices
   What can you choose at each step?

3. Propose a rule
   Earliest finish? Largest value? Smallest cost? Best ratio?

4. Find the invariant
   What remains true after every committed choice?

5. Prove safety
   Usually with an exchange argument or a cut-style argument.

6. Analyze the cost
   Many greedy algorithms are dominated by sorting: often O(n log n).

In C#, greedy code often looks straightforward. The hard part is choosing and defending the rule.

Smallest resource that works

Another common greedy shape is:

Sort needs, sort resources, then use the smallest resource that satisfies the next need.

Example: assign cookies to children. Each child has a greed factor, and each cookie has a size. A child is satisfied if cookieSize >= greed.

The greedy rule is to satisfy the least demanding remaining child with the smallest cookie that works.

This avoids wasting large cookies on small needs.

```csharp
using System;
using System.Linq;

public class Program
{
    public static void Main()
    {
        int[] greed = { 2, 1, 3 };
        int[] cookies = { 1, 1, 2, 3 };

        Array.Sort(greed);
        Array.Sort(cookies);

        int child = 0;
        int cookie = 0;
        int satisfied = 0;

        while (child < greed.Length && cookie < cookies.Length)
        {
            if (cookies[cookie] >= greed[child])
            {
                Console.WriteLine($"Child needing {greed[child]} gets cookie {cookies[cookie]}");
                satisfied++;
                child++;
            }

            cookie++;
        }

        Console.WriteLine($"Satisfied children = {satisfied}");
    }
}
```

Commit carefully

Greedy algorithms are powerful because they turn optimization into a sequence of simple commitments.

But the rule must be justified.

Remember the progression:

• Sorting and Searching Algorithms gave you useful order.
• Dynamic Programming showed how to solve by considering alternatives and reusing answers.
• Graph Algorithms expanded your thinking to connected states.
• Greedy Algorithms ask: can one local choice be proven safe enough to skip the alternatives?

In the next lesson, Advanced Topics in OODSA, you will connect these patterns to more complex design decisions and tradeoffs.