Greedy Algorithms

Why Greedy Algorithms Matter

Now that we've covered Dynamic Programming, you know how to solve optimization problems by exploring many states and reusing answers.

Greedy algorithms are the next major interview strategy because they ask a different question:

Can we make the best-looking choice right now, commit to it, and still end up optimal?

When greedy works, it is often simpler and faster than DP. Many MAANG-style problems involving intervals, scheduling, minimum resources, and ordering can be solved this way.

The catch: greedy is not just “pick what looks good.” In interviews, the important skill is explaining why the local choice is safe.

The Greedy Pattern

A greedy algorithm repeatedly does three things:

1. Look at the current situation.
2. Choose the locally best option.
3. Commit to that choice and never revisit it.

Compared to earlier lessons:

• Backtracking explores many possible paths.
• Dynamic Programming stores answers to overlapping subproblems.
• Greedy tries to avoid both by proving one choice is always safe.

A useful mental model:

Problem state → best local choice → smaller problem → repeat

The key word is safe. A greedy choice is safe if making it cannot prevent an optimal final answer.

Classic Greedy Example: Activity Selection

Problem: given activities with start and end times, choose the maximum number of non-overlapping activities.

A tempting choice is to pick the activity that starts earliest. But that can block many shorter activities.

The proven greedy choice is:

Always pick the activity that finishes earliest among the remaining compatible activities.

Why? Finishing earlier leaves as much room as possible for future activities.

This builds directly on Sorting and Searching: we sort by end time, then make one pass.

```java
import java.util.*;

class Main {
  public static void main(String[] args) {
    int[][] activities = {
      {1, 3}, {2, 5}, {4, 7}, {1, 8}, {8, 10}, {9, 11}, {10, 12}
    };

    List<int[]> selected = maxActivities(activities);

    System.out.println("Selected activities:");
    for (int[] a : selected) {
      System.out.println("[" + a[0] + ", " + a[1] + "]");
    }
    System.out.println("Maximum count: " + selected.size());
  }

  static List<int[]> maxActivities(int[][] activities) {
    Arrays.sort(activities, (a, b) -> Integer.compare(a[1], b[1]));

    List<int[]> result = new ArrayList<>();
    int lastEnd = Integer.MIN_VALUE;

    for (int[] activity : activities) {
      int start = activity[0];
      int end = activity[1];

      if (start >= lastEnd) {
        result.add(activity);
        lastEnd = end;
      }
    }

    return result;
  }
}
```

Which observation most strongly suggests that a greedy approach might be correct?

The Interview Proof Idea

In interviews, a greedy solution usually needs a short correctness argument. Two ideas help:

1. Greedy choice property

The local choice can be part of some optimal solution.

For interval scheduling, choosing the earliest-ending activity is safe because it leaves maximum remaining time.

2. Optimal substructure

After making the greedy choice, the remaining problem has the same shape as the original problem.

After selecting one activity, we just need to solve the same problem for activities that start after it ends.

A common proof style is an exchange argument:

If an optimal solution chose something else first, we can swap in the greedy choice without making the solution worse.

True or false: If a greedy algorithm is fast and passes the sample test cases, we can assume it is optimal.

When Greedy Fails

Greedy can fail when a local choice blocks a better combination later.

For coin change, using the largest coin first works for many real-world coin systems, but not for all coin sets.

Example coins: {4, 3, 1}

Amount: 6

Greedy chooses 4, then 1, then 1 → 3 coins.

But the better answer is 3 + 3 → 2 coins.

This is why the previous Dynamic Programming lesson matters: if greedy cannot be proven safe, DP may be the better tool.

```java
import java.util.*;

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

    List<Integer> greedyCoins = greedyChange(coins, amount);

    System.out.println("Coins: " + Arrays.toString(coins));
    System.out.println("Amount: " + amount);
    System.out.println("Greedy choice: " + greedyCoins);
    System.out.println("Greedy coin count: " + greedyCoins.size());
    System.out.println("Better answer exists: [3, 3] with count 2");
  }

  static List<Integer> greedyChange(int[] coins, int amount) {
    Arrays.sort(coins);
    reverse(coins);

    List<Integer> used = new ArrayList<>();

    for (int coin : coins) {
      while (amount >= coin) {
        used.add(coin);
        amount -= coin;
      }
    }

    return used;
  }

  static void reverse(int[] arr) {
    int left = 0, right = arr.length - 1;
    while (left < right) {
      int temp = arr[left];
      arr[left] = arr[right];
      arr[right] = temp;
      left++;
      right--;
    }
  }
}
```

A common first step in many greedy interview problems is to transform the input into a helpful order.

Fill in the blank:

We often first ______ the input so the best local choice is easy to compare.

Greedy With Two Pointers

Problem: each child has a greed factor, and each cookie has a size. A child is satisfied if the cookie size is at least the child's greed factor.

Goal: satisfy as many children as possible.

Greedy idea:

1. Sort children by greed.
2. Sort cookies by size.
3. Give the smallest possible cookie to the least greedy child it can satisfy.

This reuses the Arrays and Strings two-pointer thinking and Sorting and Searching ordering tools.

```java
import java.util.*;

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

    int satisfied = findContentChildren(greed, cookies);

    System.out.println("Greed factors: " + Arrays.toString(greed));
    System.out.println("Cookie sizes: " + Arrays.toString(cookies));
    System.out.println("Children satisfied: " + satisfied);
  }

  static int findContentChildren(int[] greed, int[] cookies) {
    Arrays.sort(greed);
    Arrays.sort(cookies);

    int child = 0;
    int cookie = 0;

    while (child < greed.length && cookie < cookies.length) {
      if (cookies[cookie] >= greed[child]) {
        child++;
      }
      cookie++;
    }

    return child;
  }
}
```

Greedy Interview Checklist

When you suspect greedy, walk through this checklist:

• What am I optimizing? Count, cost, time, value, distance?
• What is the local choice? Earliest end, smallest cost, largest value, smallest sufficient item?
• Do I need sorting? Most greedy problems become clear after ordering the input.
• Can I find a counterexample? Try small tricky cases before coding.
• Can I explain safety? Use a short exchange argument or “stays ahead” reasoning.
• What is the complexity? Usually sorting dominates: O(n log n) time, plus a linear scan.

Greedy is powerful because it rewards clear thinking. In the next lesson, Graph Algorithms, some greedy ideas will reappear in graph-specific settings, but for now your focus is recognizing and justifying safe local choices.