Greedy Strategy Explained

Greedy algorithms make a sequence of locally optimal choices in the hope of reaching a global optimum. They are often very simple and fast, but they only work when the problem structure cooperates.

This article explains how to think about greedy strategies and how to avoid using them blindly.

What Is a Greedy Algorithm?

In a greedy algorithm, at each step you:

  1. Look at the current situation.
  2. Pick the choice that seems best right now according to some rule.
  3. Never reconsider that choice later.

This contrasts with DP or backtracking, which may consider multiple futures from the same state.

Greedy works when:

  • There exists an ordering or rule such that taking the locally best option never blocks a globally optimal solution.

Classic Example: Interval Scheduling

Problem:

Given intervals [start, end), select a maximum number of non‑overlapping intervals.

Greedy strategy:

  1. Sort intervals by end time ascending.
  2. Always pick the interval that finishes earliest among those compatible with current schedule.

Why it works (intuitively):

  • Finishing as early as possible leaves the most room for remaining intervals.
  • You can show, via an exchange argument, that for any optimal solution, you can replace its first interval with the earliest‑ending compatible interval without reducing the total count.

This pattern (sort + one pass + local rule) appears in many greedy problems.

How to Design a Greedy Strategy

  1. Sort or prioritize by some key:
    • End time, start time, weight / ratio, position.
  2. Walk through the items in that order.
  3. At each step, decide to take or skip based on a simple local condition.

Key questions:

  • What about the item makes it “good” to take early?
  • If I take this item now, can I ever regret it in an optimal solution?

Reasoning About Correctness

Greedy proofs usually rely on one of:

  • Exchange argument:
    • Take an arbitrary optimal solution and show you can “exchange” parts to match your greedy choices without making it worse.
  • Cut property:
    • Show that across any “cut” of the input, greedy’s choice is at least as good as any optimal solution’s choice.

You don’t always need a fully formal proof in an interview, but you should be able to:

  • Explain why your rule is safe (cannot block optimal).
  • Provide at least an intuitive exchange or cut argument.

When Greedy Shines

Common categories:

  • Interval / scheduling problems
    • Interval scheduling, meeting rooms, min number of arrows to burst balloons.
  • Resource allocation
    • Assign tasks to machines, minimize total waiting time.
  • Change‑making / coin systems (with specific coin systems like US currency).
  • Sorting‑based decisions
    • Activity selection, non‑overlapping chains, choosing minimal subsequences.

Characteristics:

  • Decisions can be made based on local information and sorted order.
  • There is a natural notion of “taking more now helps later”.

When Greedy Fails

Signs that greedy might not work:

  • A simple counterexample breaks your local rule.
  • Optimal solution depends on global interactions (e.g. knapsack with arbitrary weights and values).
  • The problem has a strong DP flavor (e.g. many overlapping subproblems, multiple interacting dimensions).

Example: 0/1 Knapsack

  • Greedy by value, by weight, or by value/weight ratio all fail on carefully chosen examples.
  • The correct solution is DP, not greedy.

Practical Tips for Interviews

  • If you propose a greedy rule, immediately test it on:
    • Small random examples.
    • Adversarial / edge cases you can think of.
  • If you quickly find a counterexample, don’t be afraid to say:
    • “This greedy rule doesn’t work; we probably need DP/backtracking instead.”

Interviewers care more about your reasoning than about clinging to a broken idea.

Checklist: When to Try Greedy

Ask yourself:

  1. Can I sort the items by some meaningful key?
  2. After sorting, does a one‑pass algorithm with a simple local rule almost work?
  3. Can I argue that if an optimal solution didn’t follow my rule, I could swap something and not make it worse?

If yes, it’s worth trying a greedy approach first. If the justification feels forced or you keep finding counterexamples, switch to DP or another pattern.