Skip to main content

Greedy Fundamentals

Essential concepts and principles for understanding and applying greedy algorithms.

Greedy choice property​

  • Definition: Globally optimal solution can be reached by making locally optimal choice
  • Local Optimum: Best choice at current step
  • Global Optimum: Best overall solution
  • Irrevocable: Once choice is made, it cannot be undone

Optimal substructure​

  • Definition: Optimal solution contains optimal solutions to subproblems
  • Recursive Structure: Problem can be broken down into smaller similar problems
  • Independence: Subproblems are independent of each other
  • Combination: Optimal solutions to subproblems combine to form optimal solution

Proof techniques​

  • Exchange Argument: Show that any other solution can be improved
  • Cut and Paste: Replace part of solution with greedy choice
  • Induction: Prove by mathematical induction
  • Contradiction: Assume non-greedy solution is optimal and derive contradiction

When to use greedy​

  • Greedy Choice Property: Problem has greedy choice property
  • Optimal Substructure: Problem has optimal substructure
  • No Backtracking: Solution doesn't require backtracking
  • Local Optimum: Local optimum leads to global optimum

Common greedy patterns​

  • Sorting First: Sort input by some criteria
  • Selection: Select elements based on greedy criteria
  • Interval Problems: Handle intervals with greedy selection
  • Resource Allocation: Allocate resources greedily