Greedy algorithm works if a problem exhibits the following two properties:
- Greedy Choice Property: A globally optimal solution can be reached at by creating a locally optimal solution. In other words, an optimal solution can be obtained by creating "greedy" choices.
- Optimal substructure: Optimal solutions contain optimal sub-solutions. In other words, answers to sub-problems of an optimal solution are optimal.
Example:
- Machine scheduling
- Fractional Knapsack Problem
- Minimum Spanning Tree
- Huffman Code
- Job Sequencing
- Activity Selection Problem