Chapter 4 – Greedy Algorithms

My notes on the assigned sections of Chapter 4 of Algorithm Design by Jon Kleinberg and Éva Tardos. This chapter details greedy algorithms. A greedy algorithm is an algorithm that “builds up a solution in small steps, choosing a decision at each step myopically to optimize some underlying criterion.”

The main challenge in designing a good greedy algorithm is deciding which rule to use for the selection process. For interval scheduling, some rules that might seem good are minimal start time and the smallest interval time, but the best rule is to use the request that finishes first. This way, we maximize the time left over to service the other requests.