The Greedy Paradigm
Construct a solution iteratively, via a sequence of myopic decisions, and hope that everything works out in the end.
Features and Bugs of the Greedy Paradigm
- Easy to come up with one or more greedy algorithms
- Easy to analyze the running time
- Hard to establish correctness
Warning: most greedy algorithm are not always correct.
A Scheduling Problem
In scheduling, the jobs have different length, which is the amount of time required to process the job, also each job has a weight, with higher weights corresponding to higher-priority jobs.
These two scoring functions lead to two different greedy algorithms:
- GreedyDiff: schedule the jobs in decreasing order of (weight — length)
- GreedyRatio: schedule the jobs in decreasing order of (weight/ length)
