What does 'greedy choice criterion' mean?

AlgorithmsJunior~3 min read

Short answer

A greedy-choice criterion is a property of an optimization problem in which, at each step, it is safe to make the locally best feasible choice so that it belongs to some optimal solution. If this property holds, a greedy algorithm that repeats the locally optimal choice leads to the global optimum.

Detailed explanation

What this means formally

A greedy algorithm builds a solution step by step, each time choosing the "best right now" element by some rule. A greedy-choice criterion is the justification that such a local choice will not ruin the ability to reach the global optimum. This usually rests on two properties of the problem:

Optimal substructure: the problem's optimal solution contains optimal solutions of its subproblems.
Greedy-choice property: there exists an optimal solution that starts with some locally optimal choice; hence, making this choice does not lose optimality.

When the criterion holds: typical problems

Selecting non-overlapping intervals (activity selection): always take the interval with the earliest end time - gives the maximum number of compatible intervals.
Minimum spanning trees (Kruskal/Prim): the "cut property" guarantees that at each step it is safe to take the minimum edge crossing some cut.
Shortest paths from a source with non-negative weights (Dijkstra): always pick the vertex with the minimum current distance estimate; with non-negative weights this is safe.
Huffman coding: at each step, merge the two lowest-frequency nodes - this leads to an optimal prefix code.
Coin change for "canonical" denominations (for example, 1, 5, 10, 25): always take the largest suitable coin - optimal.

When it does not work: counterexamples

Coin change with denominations {1, 3, 4}: for sum 6, greediness gives 4+1+1 (3 coins), the optimum is 3+3 (2 coins).
0/1 knapsack: taking the item with the highest value/weight is often not optimal (greediness only works for the fractional knapsack).
Shortest paths with negative weights: Dijkstra's greedy choice is incorrect; Bellman-Ford is needed.

How the correctness of a greedy algorithm is proved

Exchange argument: shows that any optimum can be "fixed" by replacing its first choice with the greedy one, without worsening the result.
Cut/cycle property (for graphs): the minimum edge across a cut is always safe; the maximum edge on a cycle is unsafe (for MST).
Matroid structure: if the set of feasible solutions forms a matroid, the greedy algorithm is optimal for any monotone weight function.
Induction over steps: after each greedy step, a subproblem of the same type remains, to which the same argument applies.

Template for designing a greedy solution

Formulate the goal (what is being maximized/minimized).
Define the set of feasible solutions and constraints.
Propose a local selection rule (the greedy step).
Prove the greedy-choice property (usually by exchange) and optimal substructure.
Implement: sorting/data structures plus a single-pass selection.
Estimate complexity and consider edge cases.

Example: selecting the maximum number of non-overlapping intervals

Rule: always take the next interval with the minimum end time that is compatible with those already chosen.

// intervals: an array of objects { start, end }
function selectActivities(intervals) {
  // 1) Sort by end time
  intervals.sort((a, b) => a.end - b.end);

  const result = [];
  let lastEnd = -Infinity;

  // 2) Go left to right, adding the first compatible interval
  for (const it of intervals) {
    if (it.start >= lastEnd) {
      result.push(it);
      lastEnd = it.end;
    }
  }
  return result; // the largest set of non-overlapping intervals
}

// Example
const input = [
  { start: 1, end: 4 },
  { start: 3, end: 5 },
  { start: 0, end: 6 },
  { start: 5, end: 7 },
  { start: 8, end: 9 },
  { start: 5, end: 9 },
];
console.log(selectActivities(input));

Complexity: O(n log n) for sorting and O(n) for the pass. Correctness: exchange argument - if the optimal solution does not start with the interval with the earliest end, it can be replaced with such an interval without reducing the solution's size.

Counterexample to greediness (coin change)

The greedy choice "take the largest coin that does not exceed the remainder" is not always optimal:

Denominations: {1, 3, 4}
Sum: 6
Greedy: 4 + 1 + 1 = 3 coins
Optimum: 3 + 3 = 2 coins

Interview checklist

What are we optimizing, and what are the constraints?
What local rule seems natural?
Can the greedy-choice property be proved (by exchange/cut/matroid)?
Are there counterexamples? If so, dynamic programming/search/approximation is needed.
Complexity and data structures (sorting, priority queues).

Not to be confused with "greedy" in regular expressions

The term "greedy" is also used for quantifiers in regular expressions (greedy/lazy matches), but a "greedy-choice criterion" refers specifically to the correctness of greedy algorithms in optimization problems.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.