[Greedy]

Greedy Algorithms work step-by-step, and always choose the steps which provide immediate profit/benefit. It chooses the “locally optimal solution”, without thinking about future consequences.

Greedy algorithms may not always lead to the optimal global solution, because it does not consider the entire data. The choice made by the greedy approach does not consider future data and choices.

In some cases making a decision that looks right at that moment gives the best solution (Greedy), but in other cases, it doesn’t. The greedy technique is used for optimization problems (where we have to find the maximum or minimum of something). The Greedy technique is best suited for looking at the immediate situation .

 

Greedy choice property: 

Greedy algorithms make the choice that looks best at the moment based on a heuristic, such as the smallest, largest, best ratio, and so on. This algorithm only gives one shot at finding the solution and never goes back to consider other options. 

 

1. Take a sample from the input data (usually in a data structure like array/list, tree, graph).
2. Greedy choice: use a heuristic function that will choose the best candidate. E.g., Largest/smallest number, best ratio, etc.
3. Reduce the processed input and repeat step #1 and #2 until all data is gone.
4. Return solution.
5. Check correctness with different examples and edge cases.