Background
An algorithm is greedy if it tries to find the best local solution at each step with the hope that the best global solution will be found in the process. And sometimes this works!
Schedule as many seminars as possible
Let’s say you were at Comic-con and wanted to ensure that you’re day was as full as possible. After all, you want to maximize your experience.
And these are your options:
| Seminar | Start | End |
|---|---|---|
| Artist meet | 9 AM | 10 AM |
| Interview with Stan Lee | 9:30 AM | 10:30 AM |
| V for Vendetta cast | 10 AM | 11 AM |
| Ironman preview | 10:30 AM | 11:30 AM |
| Spiderman preview | 11 AM | 12 PM |
This looks something like this:
We need to look at a few more examples to come up with a strategy of picking the right seminars. Let’s have a look at a few generic examples of events below.
But let’s look closer at why we pick these and how we would formalize it.
Breakdown
If we just picked the shortest events, that may not always be optimal. Picking the ones that start the earliest is
also not enough.
Steps
- Pick the seminar with the earliest end-time
- Now you pick a seminar that starts right after this one. If you get more than one, then pick the one that ends soonest.
A good example is the Task Scheduler.