Greedy Algorithms
Greedy algorithms are a problem-solving method used in programming tests.
why the word greedy?
Greedy algorithms make final decisions based on a global rule.
- Some values are greedy and beat other values.
- You decide based on the values in the current step.
- You throw away past decisions.
Greedy problems come in two types.
| Type | Idea |
|---|---|
| Step greedy | choose next best action |
| Structural greedy | identify dominating constraint and build around it |
Examples
- CPU Task scheduling - you pick the dominating constraint first.
- Increasing triple sequence - each step just takes the best so far.