A greedy algorithm builds a solution by choosing what looks best at each step, without generally revisiting earlier choices. It hopes that locally best moves add up to a globally good result. section 10.1 section 10.9
Scheduling classes
To fit the most classes into one room, repeatedly choose the class that ends soonest and does not conflict with those already scheduled. This finds the optimal schedule in the example: Art, Math, and Music. section 10.1
When the local choice misses the best answer
With a 35-pound knapsack, taking the most expensive item first yields $3,000 in goods. Choosing a laptop and guitar instead yields $3,500, so the greedy choice is not always optimal. section 10.2
When finding an exact answer would take too long, greedy choices can provide a fast approximation. For set covering, repeatedly choose the station covering the most states still uncovered; this approach runs in O(n²) time for n stations. section 10.4 section 10.8
while states_needed:
best_station = None
states_covered = set()
for station, states in stations.items():
covered = states_needed & states
if len(covered) > len(states_covered):
best_station = station
states_covered = covered
states_needed -= states_covered
final_stations.add(best_station)
See the loop that repeatedly picks the station covering the most remaining states and updates the uncovered set. section 10.8
Greedy choices also work for fractional knapsack: take as much as possible of the most valuable item, then move to the next. Unlike the all-or-nothing dynamic-programming approach described for whole items, this handles partial items. section 11.9
