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