Greedy Algorithms
Make the locally best choice at every step, and learn how to check that this really gives the best overall answer.
The problem
A greedy algorithm builds an answer one step at a time. At each step it takes the choice that looks best right now and never changes its mind later.
A classic example, called activity selection:
- You have one meeting room and meeting requests, each with a start time and an end time.
- Two meetings cannot overlap. A meeting that ends at time 5 and one that starts at time 5 are fine together.
- Choose as many meetings as possible.
1 of 11