Greedy Algorithms
Pick the locally best choice at every step. Learn the 3 topics below step by step with interactive visualizations.
A greedy strategy that always uses the largest coin first to make change. It's optimal when the denominations are multiples of one another (e.g. 500·100·50·10), but it doesn't guarantee the fewest coins for arbitrary denominations.
O(n)A greedy problem where picking activities by earliest finish time lets you select the most non-overlapping activities. Sort by finish time, then adopt only the ones that don't overlap the previously chosen activity.
O(n log n)Compresses data by giving frequent characters short bit codes and rare ones long codes. A greedy strategy that repeatedly merges the two lowest-frequency nodes into a tree produces an optimal prefix code.
O(n log n)