Skip to main content

Classic Greedy Problems

Fundamental greedy algorithm problems that demonstrate key principles and techniques.

Activity selection​

  • Problem: Select maximum number of non-overlapping activities
  • Greedy Choice: Select activity with earliest finish time
  • Proof: Exchange argument shows this choice is optimal
  • Time Complexity: O(n log n) for sorting

Fractional knapsack​

  • Problem: Fill knapsack with maximum value (fractions allowed)
  • Greedy Choice: Select item with highest value-to-weight ratio
  • Proof: Any other solution can be improved by swapping
  • Time Complexity: O(n log n) for sorting

Huffman coding​

  • Problem: Construct optimal prefix-free code for data compression
  • Greedy Choice: Merge two least frequent characters
  • Proof: Optimal substructure and greedy choice property
  • Time Complexity: O(n log n) using priority queue

Minimum spanning tree​

  • Problem: Find minimum weight tree connecting all vertices
  • Greedy Choice: Add edge with minimum weight that doesn't create cycle
  • Algorithms: Kruskal's and Prim's algorithms
  • Proof: Cut property and cycle property

Shortest path (Dijkstra)​

  • Problem: Find shortest path from source to all vertices
  • Greedy Choice: Select vertex with minimum distance
  • Proof: Once vertex is processed, its distance is final
  • Time Complexity: O((V + E) log V) with binary heap