Feb 21, 2012
Greedy Algorithm
Interval Scheduling
Sort by finish time -> take each job if compatible with the ones already taken
Running time: O(nlogn)
The solution need not be unique
Interval Partitioning
Sort by starting time -> schedule lecture in compatible classroom
Running time: O(nlogn)
Minimize Lateness
Earliest deadline first (not processing time or slack)
Greedy schedule has no idle time
Inversions: greedy schedule has no inversion
Coin Changing
Greed is optimal for US coinage(1, 5, 10, 25, 100)
Greed is not optimal US postal denomination
Dijkstra / Prim / Kruskal’s algorithms are greedy algorithms
