Loading...

Back to Algorithms

Greedy Algorithms

Learn to solve optimization problems by making the best local choice at each step. Master the greedy approach and understand when it leads to globally optimal solutions.

Greedy Algorithm Principles

Greedy Choice Property

A globally optimal solution can be reached by making locally optimal choices

Example: In activity selection, choosing earliest finish time is always optimal

Optimal Substructure

An optimal solution contains optimal solutions to subproblems

Example: In MST, removing any edge gives optimal spanning tree for remaining vertices

No Backtracking

Once a choice is made, it is never reconsidered or undone

Example: Dijkstra never updates distance to visited vertices

Greedy vs Other Approaches

Greedy Algorithm

• Make locally optimal choice
• Never reconsider decisions
• Fast and simple
• Works for specific problems

Dynamic Programming

• Consider all subproblems
• Optimal substructure
• Slower but more general
• Guaranteed optimal solution

Brute Force

• Try all possibilities
• Guaranteed optimal
• Exponential time
• Impractical for large inputs

Classic Greedy Algorithms

Activity Selection Problem

Select maximum number of non-overlapping activities

Earliest Finish Time

Sort by finish time, select greedily

Proof Technique:

Exchange argument - greedy choice is always part of optimal solution

Meeting scheduling, Resource allocation

Fractional Knapsack

Maximize value by taking fractions of items within weight limit

Highest Value-to-Weight Ratio

Sort by value/weight ratio, take greedily

Proof Technique:

Cut-and-paste argument proves optimality

Resource optimization, Investment portfolio

Huffman Coding

Optimal prefix-free binary encoding for data compression

Minimum Frequency First

Build tree bottom-up merging least frequent nodes

Proof Technique:

Optimal substructure and greedy choice property

Data compression, File encoding

Job Scheduling with Deadlines

Schedule jobs to maximize profit within deadlines

Highest Profit First

O(n²) / O(n log n)

Sort by profit, schedule at latest possible time

Proof Technique:

Exchange argument with disjoint set optimization

Project management, CPU scheduling

Coin Change (Greedy)

Make change with minimum number of coins (for canonical systems)

Largest Denomination First

Always pick largest coin ≤ remaining amount

Proof Technique:

Works only for canonical coin systems (US, Euro)

Cash registers, Vending machines

Kruskal's MST Algorithm

Find minimum spanning tree using edge-based greedy approach

Minimum Weight Edge First

Sort edges, add if no cycle (union-find)

Proof Technique:

Cut property - minimum edge crossing any cut is in MST

Network design, Circuit layout

Prim's MST Algorithm

Build minimum spanning tree by growing from starting vertex

Minimum Edge from Tree

Maintain tree, add minimum edge to new vertex

Proof Technique:

Cut property applied to tree vs non-tree vertices

Network infrastructure, Road construction

Dijkstra's Shortest Path

Find shortest paths from source using greedy edge relaxation

Closest Unvisited Vertex

O((V + E) log V)

Maintain distances, always relax from closest vertex

Proof Technique:

Optimal substructure with non-negative weights

GPS navigation, Network routing

Gas Station Problem

Find starting gas station to complete circular tour

Reset at Deficit

Track surplus, reset start when deficit occurs

Proof Technique:

If solution exists, greedy choice finds it

Route planning, Resource planning

Proof Techniques for Greedy Algorithms

Exchange Argument

Show that any optimal solution can be transformed to greedy solution without losing optimality

Example Application:

Activity Selection: Exchange any activity with later finish time for earlier one

Proof Steps:

1. Start with optimal solution
2. Exchange non-greedy choice with greedy one
3. Prove new solution is still optimal

Cut-and-Paste

Remove part of optimal solution and replace with greedy choice

Example Application:

Fractional Knapsack: Replace any item with lower ratio with higher ratio item

Proof Steps:

1. Remove suboptimal part
2. Replace with greedy choice
3. Show improvement or equality

Stays Ahead

Prove greedy algorithm always maintains better or equal state than any other algorithm

Example Application:

Dijkstra: Greedy distances are always ≤ actual shortest distances

Proof Steps:

1. Define invariant
2. Prove invariant maintained
3. Show invariant implies optimality

When Does Greedy Work?

✅ Greedy Works Well

Scheduling Problems

Activity selection, job scheduling with deadlines

Graph Problems

MST (Kruskal, Prim), shortest path (Dijkstra)

Optimization with Ratios

Fractional knapsack, Huffman coding

Canonical Systems

Coin change for standard currencies

❌ Greedy Fails

0/1 Knapsack

Cannot take fractions - need DP instead

Longest Path Problem

Greedy choices don't lead to global optimum

Non-canonical Coin Systems

Example: coins [1, 3, 4] for amount 6

Traveling Salesman

Nearest neighbor heuristic not optimal

Practice Greedy Algorithms

Visualize greedy choices and see how local optimizations lead to global solutions

Start with Activity Selection

Back to Dynamic Programming Next: Divide & Conquer