What problems are classically solved with a greedy algorithm?

AlgorithmsJunior~4 min read

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));

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

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

Short Answer

Interview ready

Premium

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