When Greed Is Good: Greedy Algorithms and Matroids

A hospital scheduler must fit as many operations as possible into one theatre tomorrow. Her predecessor booked the shortest first; her colleague books the earliest start. Both are wrong, and the right rule takes one sentence and a proof you can follow in your head. Part six of The Deep End's algorithms series is about greedy algorithms: when taking the best choice right now is provably optimal, as in David Huffman's 1951 term paper that beat his professor; when it fails, as with shillings and half crowns; when it is provably close enough; and the 1935 abstraction, the matroid, that says exactly when greed is good. Lucía, Dimitri and the hospital are fictional; the history and results are sourced in the fact-check log. Chapters 00:00:00 Cold open: the theatre list 00:02:57 What greedy means 00:04:29 Lucía's three rules 00:08:03 When the rooms multiply 00:09:25 Huffman's term paper 00:15:03 The coins in your pocket, and the coins in your grandmother's 00:18:11 Where Huffman's optimality stops 00:21:09 Matroids: the theory of when greed is good 00:26:31 Dijkstra is greedy too 00:27:44 Earliest deadline first, and its cliff 00:30:04 Gold dust and the fractional knapsack 00:31:57 Belady's cache and the furthest future 00:34:38 Filling up the tank 00:36:05 When greedy is not optimal but provably close 00:38:40 Diminishing returns 00:41:31 Greedy that wanders off 00:44:15 Greedy in machines you use 00:46:46 How to know you can trust a greedy rule 00:50:10 Lucía's whiteboard 00:51:36 When not to use greedy algorithms 00:53:17 What to remember Created by Sankalp Thakur. A Transient Labs production. Website: https://transientlabs.ai GitHub: https://github.com/sankalpsthakur X / Twitter: https://x.com/sankalpsthakur LinkedIn:   / sankalpthakur   Hugging Face: https://huggingface.co/sankalpsthakur Scripts generated with Claude Opus. Synthetic narration generated with Kokoro. Reviewed, listened to, and approved by Sankalp Thakur.