Greedy algorithms are about making locally optimal choices.
They are not "brute force" algorithms or inefficient ones.
In fact, greedy algorithms are almost always faster. They are faster because they consider only local information instead of the entire data set. In exchange for that, a greedy algorithm may produce non-optimal answers.
I think of change making algorithm when working retail. Greedy is you always use the largest coin you can, and then the next largest and so on. It works with sensible coin denominations but there are sets of coins where the greedy algorithm is not optimal.
Looking at cases where greedy isn't optimal, I see two patterns. Either:
* there are two coins close in value (ratio of less than 2), e.g. both 20¢ and 25¢; or
* there is a "missing" coin at the GCD of two larger coins.
I'm pretty sure you can precompute extra "virtual coins" (e.g. 40¢) to make greedy optimal again, but you have to place restrictions on how many of them you're allowed to use.