Greedy algorithms are among the most intuitive and efficient strategies in algorithm design. This blog dives deep into the greedy approach, explains when it works, when it fails, and walks through popular problems that can (and can’t) be solved with greedy techniques.

🧮 What is a Greedy Algorithm?

A greedy algorithm solves a problem by making the locally optimal choice at each step, with the hope that this leads to a globally optimal solution.

It never reconsiders choices once made. This simplicity often leads to efficient algorithms with linear or polynomial time complexity.

🔍 When to Use a Greedy Algorithm

You can typically apply a greedy strategy when:

  • The problem exhibits greedy-choice property (local optimum leads to global optimum).
  • The problem has optimal substructure (optimal solution can be built from optimal subproblems).
  • You don’t need to backtrack or try all combinations.

📈 Common Greedy Problems and Their Strategies

1. Activity Selection Problem

  • Goal: Schedule the maximum number of non-overlapping activities.
  • Greedy Strategy: Always pick the activity that finishes the earliest.
  • Why it works: Picking the earliest finishing task leaves the most room for others.

2. Fractional Knapsack Problem

  • Goal: Maximize value within a weight limit. You can take fractions of items.
  • Greedy Strategy: Take the item with the highest value-to-weight ratio first.
  • Why it works: Fractional taking allows a truly optimal greedy decision.

3. 0/1 Knapsack Problem

  • Goal: Maximize value within a weight limit. Items must be taken whole.
  • Greedy? ❌ No. Greedy fails here. You may need to skip a high-ratio item to get better total value. Use Dynamic Programming.

4. Coin Change (Minimum Coins)

  • Goal: Use the fewest coins to make a target sum.
  • Greedy? ❌ Not always. Works with standard denominations like [1, 5, 10, 25], but fails for custom sets like [1, 3, 4]. Use DP.

5. Jump Game II

  • Goal: Find the minimum number of jumps to reach the end of an array.
  • Greedy Strategy: Jump to the farthest reachable index within the current range.
  • Why it works: You explore the widest area possible in each jump.

6. Candy Distribution

  • Goal: Distribute candies to children such that higher-rated kids get more candies than neighbors.
  • Greedy Strategy: Left-to-right and right-to-left passes to ensure conditions.
  • Why it works: Enforces local constraints from both sides.

7. Reorganize String

  • Goal: Rearrange characters so that no two adjacent characters are the same.
  • Greedy? ❌ Not purely. Requires a max-heap to alternate characters by frequency.

8. Minimum Platforms (Train Schedule)

  • Goal: Find the minimum number of platforms needed for all trains.
  • Greedy Strategy: Sort arrivals and departures, use two pointers to allocate platforms.

9. Task Scheduler

  • Goal: Schedule tasks with cooldown such that same task has a gap of n units.
  • Greedy Strategy: Always place the most frequent task and fill idle slots.

10. Interval Partitioning (Meeting Rooms / Class Scheduling)

  • Goal: Find the minimum number of meeting rooms required.
  • Greedy Strategy: Sort by start time and use a min-heap to track end times.

11. Maximum Subarray (Kadane’s Algorithm)

  • Goal: Find the contiguous subarray with the maximum sum.
  • Greedy Strategy: Extend the current subarray if the sum is positive; otherwise, restart.

12. Partition Labels

  • Goal: Divide a string into as many parts as possible so that each letter appears in at most one part.
  • Greedy Strategy: Track the last occurrence of each character and cut when all are covered.

🔎 How to Identify Greedy-Friendly Problems

Look for these hints:

  • The problem asks for max/min number of steps, resources, or coverage.
  • Choices can be made in order, often after sorting.
  • Local decisions naturally lead to a global solution.

🔮 Final Tips

  • Always test greedy against edge cases!
  • If greedy fails, try Dynamic Programming or Backtracking.
  • Combine greedy with heaps or sorting for powerful solutions.

📚 Practice Problems:

  • Leetcode 45: Jump Game II
  • Leetcode 435: Non-overlapping Intervals
  • Leetcode 134: Gas Station
  • Leetcode 621: Task Scheduler
  • Leetcode 253: Meeting Rooms II
  • Leetcode 135: Candy
  • Leetcode 56: Merge Intervals
  • Leetcode 763: Partition Labels

Keep practicing and trust the greedy strategy—but verify before you commit! 🚀