**Greedy algorithm** makes the locally optimal choice at each step to find the overall optimal way to solve the entire problem. If both of the properties below are true, a greedy algorithm can be used to solve the problem.

**Greedy choice property:**A global optimal solution can be reached by choosing the optimal choice at each step.**Optimal substructure:**A problem has an optimal substructure if an optimal solution to the entire problem contains the optimal solutions to the sub-problems.

Critical Ideas to Think

- In many problems, a greedy strategy does not produce an optimal solution.
- Proving that a greedy algorithm is correct is more of an art than a science. Usually, coming up with an algorithm might seem to be trivial, but proving that it is actually correct, is a whole different problem.

Applications of greedy algorithms:Huffman Encoding, Shortest Path Algorithms, Minimum Spanning Tree, Travelling Salesman Problem, Job Scheduling Problem, Graph Vertex Cover etc .