The question this module answers: when can you commit to the choice that looks best right now, and never look back? Dynamic programming (module 12) considers every choice at every step and keeps the best. A greedy algorithm picks one choice by a simple rule (shortest first, earliest end first, farthest reach first) and moves on. When it works it's usually a sort plus a single pass, O(n log n). When it doesn't, it's silently wrong, which is why every greedy needs a proof or, at minimum, a brute-force test.
ML context.
- Scheduling and serving: processing short requests first minimises average latency (this lesson's running example); packing jobs onto GPUs and merging time ranges (lessons 14.2–14.6).
- Decoding: greedy decoding picks the most likely token at each step; beam search exists because that greedy isn't optimal for the whole sequence.
- Feature and model selection: forward selection adds the single best feature at each step, a greedy with no optimality guarantee in general.
- Compression: Huffman coding, which builds optimal prefix codes by repeatedly merging the two rarest symbols.
1. The running problem: order jobs to minimise average finishing time
Task: n jobs must run one at a time on one GPU. Job i takes d[i] seconds. A job's completion time is when it finishes.
Choose an order that minimises the sum (equivalently the average) of completion times.