Suggest an edit

Improve this article

Refine the answer for “What is a greedy algorithm?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## Short answer

A greedy algorithm is an approach that makes the locally best (most advantageous) choice at each step, without reconsidering decisions already made, hoping that the sequence of such choices leads to a globally optimal solution.

## Detailed breakdown

### Definition and intuition

Greedy algorithms build a solution step by step, each time choosing the option that looks best "here and now" by some criterion (a greedy heuristic). Key feature: decisions are irrevocable - once an element is chosen, it is never reconsidered.

### Key idea

- Local optimum: pick the best next step by the metric.
- Irrevocability: decisions are locked in and never rolled back.
- Proof: usually via an exchange argument or induction.

### When greediness gives the optimum

- There is optimal substructure: the problem's optimum is built from the optima of subproblems.
- The greedy-choice property holds: there exists an optimal solution that starts with a greedy step.
- Classic examples:
  - Selecting non-overlapping intervals (activity selection) - sort by earliest end time.
  - Minimum spanning tree: Kruskal/Prim.
  - Shortest paths: Dijkstra with non-negative weights.
  - Huffman coding.
  - Coin change with canonical denomination systems (e.g., 1, 2, 5, 10, ...).

### When greediness does not work

- 0/1 knapsack: a greedy choice by value/weight does not guarantee the optimum.
- Coin change for arbitrary denominations, e.g. [1, 3, 4] and sum 6: greedy gives 4+1+1 (3 coins), the optimum is 3+3 (2 coins).
- Shortest paths with negative edges - Bellman-Ford is needed.
- Weighted interval scheduling - dynamic programming is required.

### Template for designing a greedy solution

1. Formulate the greedy-choice metric (what "most advantageous" means).
2. Sort the data or prepare a structure for quickly picking the best candidate.
3. Iterate, each time making the greedy choice and locking it in.
4. Prove correctness: an exchange argument or induction plus the optimal-substructure property.
5. Estimate complexity: usually O(n log n) due to sorting or priority-queue work.

### Example 1: Selecting non-overlapping intervals

Problem: choose the maximum number of non-overlapping intervals. Greedy heuristic: always take the interval with the earliest end time.

```
function selectActivities(intervals) {
  // intervals: [{ start: number, end: number }]
  intervals.sort((a, b) => a.end - b.end);
  const result = [];
  let currentEnd = -Infinity;
  for (const it of intervals) {
    if (it.start >= currentEnd) {
      result.push(it);
      currentEnd = it.end;
    }
  }
  return result; // The largest set of non-overlapping intervals
}

// Example
const intervals = [
  { start: 1, end: 3 },
  { start: 2, end: 5 },
  { start: 0, end: 6 },
  { start: 5, end: 7 },
  { start: 8, end: 9 },
  { start: 5, end: 9 }
];
console.log(selectActivities(intervals));
// Complexity: O(n log n) due to sorting; proof via an exchange argument.
```

### Example 2: Coin change (canonical system)

Greedy heuristic: always take the largest possible denomination. Correct for canonical systems (e.g., 1, 2, 5, 10).

```
def greedy_change(amount, coins):
    coins = sorted(coins, reverse=True)
    result = []
    for c in coins:
        cnt = amount // c
        if cnt > 0:
            result.append((c, cnt))
            amount -= cnt * c
    return result

# Example
print(greedy_change(28, [1, 2, 5, 10]))
# Output: [(10, 2), (5, 1), (2, 1), (1, 1)]
# Note: for arbitrary denominations the greedy approach can be suboptimal.
```

### Correctness proof (sketch): exchange argument

Idea: compare the greedy solution G with an optimal one O. We show that O can be transformed step by step into a solution that starts with the greedy choice, without worsening its quality. Repeating the transformation yields a solution equal to G, hence G is optimal. For example, in the interval problem, any optimal set can be rearranged so that its first interval ends no later than the greedy one, without reducing the set's size.

### Strengths and weaknesses

- Pros: simple to implement, fast (often O(n log n)), low memory usage.
- Cons: does not always guarantee the optimum; a proof or counterexample matters.

### Quick interview cheat sheet

- State the greedy criterion and explain why it is reasonable.
- Name the cases where it applies (intervals, MST, Dijkstra >= 0, Huffman).
- Give a counterexample where greediness breaks (0/1 knapsack, coins [1,3,4]).
- Briefly describe the proof via the exchange argument.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts710 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.