Greedy

Greedy was the topic I dreaded most for a long time. Not because the code is complicated, most greedy solutions are actually pretty short, but because I never knew when I was allowed to use it. Like how do you know a greedy choice won't come back to bite you later. The answer I landed on was asking one thing before committing to a greedy approach. If I make the locally best choice right now, does it ever block me from a better global answer. If no, greedy works. If I can construct even one example where it fails, greedy is wrong and I need DP or something else. That sounds simple and it kind of is, but it took me way too long to get there because I was trying to memorize which problems are greedy instead of understanding why greedy works at all. The classic example is interval scheduling. You want to fit as many non overlapping intervals as possible. Greedy works here because always picking the interval that ends earliest never blocks you from picking more later. Once you see that logic once it starts showing up in other problems too. Where greedy fails is when early choices have consequences that aren't obvious immediately. Coin change with arbitrary denominations is the textbook example. Greedy picks the biggest coin first and it works for standard currency but breaks completely with weird denominations. That's when you need DP. What actually helped was doing greedy and DP problems side by side for a week. Seeing where one works and the other doesn't makes the distinction way clearer than any explanation. What topic took you the longest to feel like you actually understood it and not just memorized it?