Job Sequencing with Deadlines (Greedy on a Matroid)

Schedule unit-time jobs for maximum profit by taking them in decreasing-profit order and placing each in the latest free slot before its deadline — provably optimal because the feasible sets form a matroid.