Suggest an edit

Improve this article

Refine the answer for “What problems are classically solved with 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

Greedy algorithms are classically applied where the locally best choice leads to a globally optimal solution (the greedy-choice property and optimal substructure hold). Typical problems:

- Interval scheduling (maximum number of non-overlapping intervals, "activity selection")
- Point cover for intervals (minimum number of points/arrows to "pierce" intervals/circles)
- Fractional knapsack
- Coin change for canonical denomination sets (e.g., {1, 2, 5, 10, 25, 50})
- Huffman codes (optimal prefix codes/optimal file merging)
- Minimum spanning tree (Kruskal, Prim)
- Shortest paths with non-negative weights (Dijkstra)
- Job scheduling with deadlines and profit (unit duration)
- Interval partitioning (minimum number of resources/rooms)
- Route with the minimum number of refuels (greedily take the largest available fuel stop along the way)
- Approximations: set cover, vertex cover, and others (greedy gives approximation guarantees)

## Detailed breakdown, ideas, and correctness

### 1) Interval scheduling (maximum number of non-overlapping intervals)

Problem: select the maximum number of non-overlapping intervals (meetings/tasks). Greedy strategy: sort by end time and iterate, picking each interval whose start >= the end of the last chosen one.

- Why it works: an early finish "frees up" the most room for future intervals; an exchange argument shows that there exists an optimal solution starting with the interval with the minimum end.
- Complexity: O(n log n) for sorting.

```
// JS: maximum number of non-overlapping intervals (activity selection)
function selectMaxNonOverlapping(intervals) {
  const arr = intervals.slice().sort((a, b) => a.end - b.end);
  const chosen = [];
  let lastEnd = -Infinity;
  for (const it of arr) {
    if (it.start >= lastEnd) {
      chosen.push(it);
      lastEnd = it.end;
    }
  }
  return chosen;
}

// Example
const meetings = [
  { start: 1, end: 3 },
  { start: 2, end: 5 },
  { start: 4, end: 7 },
  { start: 6, end: 9 },
  { start: 8, end: 10 }
];
console.log(selectMaxNonOverlapping(meetings));
```

### 2) Point cover for intervals (minimum number of "arrows")

Problem: choose the minimum number of points on a line so that every point covers at least one interval. Greedy: sort intervals by right end, take a point at the right end of the first interval and remove all intervals covered by it, then repeat.

Correctness: any optimal strategy can be transformed by exchange so that the first point sits at the right end of the interval with the smallest right end.

### 3) Fractional knapsack

Problem: with limited capacity, fractions of items can be taken. Greedy: sort by unit value (value/weight) and fill up while there is room, taking the last item partially.

- Why it works: the greedy-choice property holds, because replacing part of a less valuable mass with a more valuable one always improves the solution.
- Complexity: O(n log n) for sorting.

```
// JS: fractional knapsack
function fractionalKnapsack(capacity, items) {
  const arr = items
    .map(it => ({ ...it, ratio: it.value / it.weight }))
    .sort((a, b) => b.ratio - a.ratio);
  let total = 0;
  const taken = [];
  for (const it of arr) {
    if (capacity <= 0) break;
    const take = Math.min(it.weight, capacity);
    total += it.value * (take / it.weight);
    taken.push({ id: it.id, take });
    capacity -= take;
  }
  return { value: total, taken };
}

// Example
const items = [
  { id: 'A', weight: 10, value: 60 },
  { id: 'B', weight: 20, value: 100 },
  { id: 'C', weight: 30, value: 120 }
];
console.log(fractionalKnapsack(50, items));
```

### 4) Coin change (canonical denominations)

Greedily take the largest possible denomination while possible. This is optimal for "canonical" sets (for example, standard currencies), but not for arbitrary ones. Counterexample: denominations {1, 3, 4}, sum 6: greedy -> 4+1+1 (3 coins), optimal -> 3+3 (2 coins).

### 5) Huffman codes (optimal prefix codes)

Idea: repeatedly merge the two least frequent nodes into one, until a single root remains. Greediness in choosing the two minimum frequencies is provably optimal, minimizing the average code length. Implemented via a min-heap; complexity O(n log n).

### 6) Minimum spanning tree (Kruskal, Prim)

Both strategies are greedy: Kruskal adds edges in order of weight, avoiding cycles; Prim grows the tree, each time adding the lightest edge leaving the current tree. Both rely on cut/lightest-edge properties; correctness rests on the "cut property."

```
// JS: Kruskal with DSU
class DSU {
  constructor(n) { this.p = Array.from({ length: n }, (_, i) => i); this.r = Array(n).fill(0); }
  find(x) { return this.p[x] === x ? x : (this.p[x] = this.find(this.p[x])); }
  union(a, b) {
    a = this.find(a); b = this.find(b);
    if (a === b) return false;
    if (this.r[a] < this.r[b]) [a, b] = [b, a];
    this.p[b] = a; if (this.r[a] === this.r[b]) this.r[a]++;
    return true;
  }
}
function kruskal(n, edges) { // edges: [u,v,w]
  const es = edges.slice().sort((a, b) => a[2] - b[2]);
  const dsu = new DSU(n);
  const mst = [];
  let cost = 0;
  for (const [u, v, w] of es) {
    if (dsu.union(u, v)) { mst.push([u, v, w]); cost += w; if (mst.length === n - 1) break; }
  }
  return { cost, edges: mst };
}

// Example
const n = 4;
const edges = [ [0,1,1], [1,2,2], [0,2,2], [2,3,1], [1,3,3] ];
console.log(kruskal(n, edges));
```

### 7) Shortest paths (Dijkstra, non-negative weights)

Dijkstra greedily "fixes" vertices in order of increasing known path length, relying on the absence of negative edges. For negative edges greediness breaks - Bellman-Ford is needed.

### 8) Job scheduling with deadlines and profit (unit-time jobs)

Jobs with 1-slot duration and deadlines: sort by decreasing profit and place each in the latest available slot before its deadline (via DSU/array/heap). Gives the maximum profit.

### 9) Interval partitioning (minimum number of rooms/resources)

Sort intervals by start and maintain a min-heap by end time. If the room that frees up soonest becomes available before the next start, reuse it; otherwise add a new one. The number of rooms equals the heap's peak size.

### 10) Route with the minimum number of refuels

Go through stations left to right; whenever we cannot reach the next one, take from a max-heap the best of the stations already passed (the largest fuel amount). This minimizes the number of stops.

## Where greediness gives approximations

- Set cover: greedily pick the set covering the most still-uncovered elements -> an O(log n)-approximation.
- Vertex cover: greedily take vertices incident to edges -> a 2-approximation.

## When greediness does not fit (important exceptions)

- 0/1 knapsack (items cannot be split) - dynamic programming (DP) is needed.
- Coin change with arbitrary denominations - greediness can be suboptimal (counterexample above).
- Weighted interval scheduling (with profit) - greediness does not work, DP with binary search is needed.
- Shortest paths with negative weights - Dijkstra breaks.

## Practical signs that greediness might work

1. You can formulate a local choice that "does not worsen" optimality (exchange argument, cut-property, worst/best local element).
2. The problem fits a matroid (for example, spanning tree, activity selection) - a class of problems where greediness is optimal.
3. There is a natural sort order: by end time, by unit gain, by frequency, by edge weight, and so on.

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

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.