Chapter 4: Greedy Algorithms

Greedy algorithms are about choosing the best local option at every step to build a solution step by step, by always picking the option that looks best at the moment. The art lies in knowing when such locally optimal steps combine into a globally optimal result, and when they do not.

The greedy principle

The greedy principle is simple; always take the most promising next step. At each iteration we select the choice that seems best according to a specific criterion. We then commit to that choice and never reconsider it. The algorithm stops when no choices remain or the target has been reached.

Defining a greedy choice

A greedy choice is defined by a local rule such as “pick the smallest weight”, “pick the earliest finishing interval”, or “pick the largest coin value not exceeding the remaining amount”. Formally, we often write a choice like argmax { … } or argmin { … } with respect to a scoring function.

Two ingredients for correctness

Greedy correctness usually needs an optimal substructure property and a way to show that the greedy choice can appear in some optimal solution. An exchange argument swaps non-greedy decisions in an optimal solution with greedy ones without making the solution worse. If all swaps preserve optimality, the greedy solution is optimal.

Recognising problems that suit greediness

Greedy approaches work when local choices align with the structure of global optimality. Problems with matroid structure or a well behaved ordering often admit simple greedy solutions.

Interval scheduling and spanning trees

An example of a classic success is interval scheduling, with the “earliest finish time” rule being optimal. Minimum spanning trees can be built greedily using Kruskal’s or Prim’s method because safe edges can be identified locally.

A compact comparison of where greedy algorithms succeed and fail

Some problems are naturally aligned with the greedy approach, while others break under its simplicity. The following table summarises a few well-known cases and shows how the greedy choice fares in each.

Making Change and Scheduling Tasks

These are two archetypal greedy patterns that appear frequently in algorithm design. The first selects items by decreasing value that still fits a constraint, as in the coin change problem. The second selects non-overlapping items in an order that maximises compatibility, as in interval scheduling.

Greedy coin change

This method works correctly for canonical coin systems such as [1, 2, 5, 10, 20, 50, 100, 200]. It repeatedly takes the largest coin not exceeding the remaining amount to reach the total with the fewest coins. The approach fails for some non-canonical or artificial sets of denominations.

def greedy_change(amount, coins):
  result = []
  for c in sorted(coins, reverse=True):
    while amount >= c:
      amount -= c
      result.append(c)
  return result

Interval scheduling by earliest finish

This greedy method aims to maximise the number of non-overlapping intervals. Given a set of start and finish times, it repeatedly selects the interval that finishes first among those beginning after the last chosen one, ensuring the largest compatible subset.

def interval_scheduling(intervals):
  # intervals: list of (start, finish)
  intervals = sorted(intervals, key=lambda x: x[1])
  selected = []
  last_end = float("-inf")
  for s, f in intervals:
    if s >= last_end:
      selected.append((s, f))
      last_end = f
  return selected

Shortest Paths: Dijkstra’s Algorithm

Dijkstra’s algorithm is a greedy method for finding the shortest path distances from a source vertex in a weighted graph. It assumes that all edge weights are non-negative, meaning every edge represents a cost or distance that cannot reduce the total length of a path. At each step, the algorithm settles the vertex with the smallest tentative distance, which is safe because any alternative route must have an equal or greater total cost.

Core idea of Dijkstra’s algorithm

The key insight is to process vertices in order of their current shortest known distance from the source. A priority queue holds all vertices that are still candidates for improvement, ordered by these tentative distances. At each step, the vertex with the smallest distance is removed from the queue, and its outgoing edges are examined to see if any neighbouring distances can be improved. Once a vertex has been removed from the queue and processed, its shortest distance is final and will never change.

Python implementation using heapq

The following example shows a simple and efficient implementation of Dijkstra’s algorithm in Python. It uses the built-in heapq module to maintain the priority queue of vertices. The graph is represented as an adjacency list, where each vertex maps to a list of (neighbor, weight) pairs.

import heapq

def dijkstra(n, adj, source):
  # n: number of vertices 0..n-1
  # adj[u]: list of (v, w) with w >= 0
  dist = [float("inf")] * n
  dist[source] = 0.0
  pq = [(0.0, source)]
  visited = [False] * n

  while pq:
    d, u = heapq.heappop(pq)
    if visited[u]:
      continue
    visited[u] = True
    for v, w in adj[u]:
      nd = d + w
      if nd < dist[v]:
        dist[v] = nd
        heapq.heappush(pq, (nd, v))
  return dist

Why the greedy step in Dijkstra’s algorithm is safe

The safety of Dijkstra’s approach lies in its handling of non-negative edge weights. When a vertex u is removed from the priority queue, its tentative distance dist[u] is already the smallest possible among all remaining candidates. Any other route to u would involve travelling through one or more unsettled vertices and adding further non-negative edge weights, which can only increase the total distance. This guarantees that dist[u] is final, in the same way that a “safe edge” in a spanning tree cannot later be improved upon.

Limits of Greedy Choices

Greedy algorithms are powerful but not universally reliable. They can fail when a series of locally optimal decisions does not combine to form a globally optimal solution. In such cases, other approaches like dynamic programming or backtracking are needed, since these methods can examine how earlier choices affect later ones and explore combinations that greediness would overlook.

Typical failure patterns (local myopia)

Local scoring that ignores future constraints causes trouble. Coin systems with tricky denominations, knapsack with indivisible items, and some path problems with negative edges all break greedy logic.

Greedy versus dynamic programming

Choosing between these two strategies depends on the structure of the problem. Greedy algorithms are quick and elegant when each local choice can be proven safe through reasoning such as an exchange or cut argument. Dynamic programming, on the other hand, trades speed for reliability by systematically exploring overlapping subproblems using recurrence relations and memoisation or tabulation. When local decisions may influence future options, dynamic programming provides the safer path to correctness.

# 0/1 knapsack needs DP; greedy by value density fails
def knapsack_01(weights, values, capacity):
  n = len(weights)
  dp = [0] * (capacity + 1)
  for i in range(n):
    w, v = weights[i], values[i]
    for c in range(capacity, w - 1, -1):
      dp[c] = max(dp[c], dp[c - w] + v)
  return dp[capacity]

As a rule of thumb, prefer greedy when you can justify that each local choice is globally safe; prefer dynamic programming when choices interact across the remainder of the instance.