Introduction to Greedy Algorithms

Greedy algorithms build a solution by always picking the locally best option, and understanding when that strategy is guaranteed to produce a global optimum is the key skill this lesson develops.

5 min read Level 2/5 #dsa#greedy#exchange-argument

What you'll learn

Explain the exchange argument used to prove a greedy choice is safe
Describe the matroid structure that guarantees greedy correctness
Contrast greedy with dynamic programming and know when to reach for each

A greedy algorithm builds its answer one piece at a time. At each step it picks the choice that looks best right now — without revisiting earlier decisions. The appeal is speed: one linear or log-linear pass, no memoization table. The risk is correctness: locally optimal moves do not always add up to a globally optimal solution.

When Greedy Works

Two complementary lenses help you decide:

Exchange argument. Suppose an optimal solution differs from the greedy solution at some step. Show that you can swap the optimal solution’s choice for the greedy choice without making things worse. If every such swap is safe, the greedy solution is at least as good as any optimal — so it is optimal.

Matroid structure. A matroid is an abstract combinatorial structure where every maximal independent set has the same size and the greedy algorithm finds the maximum-weight independent set. Spanning-tree problems, interval scheduling, and task-selection problems all fit this template. Recognizing the shape tells you greedy will work before you write a line of code.

Greedy vs Dynamic Programming

Property	Greedy	Dynamic Programming
Decisions	One pass, irrevocable	Multiple passes, revisit
State needed	O(1) or O(n)	O(n) to O(n²) table
Correctness proof	Exchange argument / matroid	Optimal substructure
Typical complexity	O(n log n)	O(n²) or O(n·k)
Fails when	Choices interfere later	Subproblems overlap

A classic failure case for greedy is the 0/1 knapsack: taking the highest value-per-weight item first does not always fill the knapsack optimally because items cannot be fractured. DP solves it correctly. Coin change with arbitrary denominations is similar — greedy works for US coins but fails for denominations like [1, 3, 4] when making change for 6.

A Quick Greedy Template

function greedySolve(items) {
  // 1. Sort by the greedy criterion
  items.sort((a, b) => greedyKey(a) - greedyKey(b));

  const result = [];
  for (const item of items) {
    // 2. Take the item if it is compatible with what we have so far
    if (isCompatible(result, item)) {
      result.push(item);
    }
  }
  return result;
}

The entire design challenge is choosing greedyKey and isCompatible. Get those right and the rest follows mechanically.

Up Next

Apply the exchange argument to a concrete problem: selecting the maximum number of non-overlapping meetings from a room-booking calendar.

Interval Scheduling →