How to Know If a Problem Can Be Solved Greedily? Let's Demystify It!

Have you ever stared at a problem and wondered: "Is greedy enough here? Or do I need DP?" ****You’re not alone. Recognizing when a greedy algorithm works is one of the most powerful skills a competitive programmer can develop.

Let’s break it down.

What is a Greedy Algorithm?

A greedy algorithm builds a solution step by step, always picking what seems best at the moment, hoping it leads to the global optimum.

How to Detect Greedy Applicability?

Here are some tell-tale signs that greedy might be the right fit:

1. You can sort the data → If sorting helps you make decisions, there's a good chance it's greedy.
2. Making a local optimal choice leads to a global solution → Classic example: Activity Selection, Huffman Encoding, Fractional Knapsack.
3. The problem wants “minimum number of…” or “maximum value of…” → These often favor greedy strategies.
4. Choices are independent of the future once made → If what you do now doesn’t affect future choices, greediness might work.
5. DP solution gives TLE, Greedy is needed for speed → Try proving the greedy choice using an exchange argument (more on that below).

Practice Problems

• 1155C — Beautiful Lyrics
• 1702D — Not a Cheap String
• 1385C — Make It Good