← All patterns

Greedy Techniques

Take the locally-best move and prove (via exchange argument or matroid) that it leads to a globally optimal solution. Sorts, heaps, and running aggregates are the usual scaffolding.

22 problems 3 Easy 12 Medium 7 Hard

Greedy chooses the locally-optimal move at each step and commits, betting that local optima compose into a global optimum. Correctness requires either an exchange argument ('any optimal can be transformed into the greedy without loss') or a matroid structure. The common scaffolding is: sort by a chosen key, then a single linear pass; or a max-heap of deferred options.

Greedy is wrong by default — *always* prove correctness for unfamiliar problems before trusting it.

When to reach for this pattern

  • 'Minimum number of X to achieve Y' / 'maximum X under budget Y'
  • Scheduling, interval covering, resource allocation
  • Activity selection, scheduling with deadlines, Huffman-style merging
  • Each decision is locally evaluable from the current state

Canonical template 

// sort by greedy key, then linear scan
sort(items.begin(), items.end(), [](auto& a, auto& b) {
    return key(a) < key(b);
});
int taken = 0, used = 0;
for (auto& it : items) {
    if (canTake(it, used)) {
        used += it.cost;
        ++taken;
    }
}
return taken;

// deferred greedy with max-heap (e.g. refueling stops)
priority_queue<int> pq;
int stops = 0, fuel = startFuel, i = 0;
while (fuel < target) {
    while (i < (int)stations.size() && stations[i][0] <= fuel) pq.push(stations[i++][1]);
    if (pq.empty()) return -1;
    fuel += pq.top(); pq.pop();
    ++stops;
}

C++ · adapt the names and types to your problem.

Common pitfalls

  • Greedy is wrong by default — always prove correctness (exchange or matroid)
  • Choosing the wrong sort key (start vs end, profit vs deadline) — many problems have a non-obvious key
  • Confusing greedy with DP — if local choices interact across steps, DP is needed
  • Local-optimal moves over a non-matroid structure (e.g. coin change with arbitrary denominations) are wrong

Related patterns

Intervals Heaps Sort and Search

Problems (22)

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.