Interview OS
Back to Algorithms & Data Structures

Library

Greedy algorithms

Locally optimal, provably global.

Optimization

Overview

Greedy algorithms commit to the best immediate choice and never reconsider. They're efficient but only correct under the greedy-choice and optimal-substructure properties — this topic focuses on recognizing when that holds.

How it works

Optimization
SortPickProveOutputBy heuristicsortGreedy steptakeExchange argoptimalResult
ClientServiceEdgeData

Step by step, with examples

  1. 1

    By heuristic

    • Order by the best local metric.
  2. 2

    Greedy step

    • Take the safe local choice.
  3. 3

    Exchange arg

    • Show no swap yields a better result.
  4. 4

    Result

    • Emit the greedy solution.
    • Example: Huffman coding

Overview

Make the best local choice and prove an exchange argument keeps it globally optimal.

When to use it

  • Interval scheduling
  • Huffman coding
  • Minimum spanning trees

Common pitfalls

  • Greedy isn't always correct — prove it
  • Sorting on the wrong key

Where this content comes from

For full transparency, this content is curated and verified from these sources:

CLRS — Introduction to AlgorithmsCurated competitive-programming archivesOppZen-authored algorithm guides