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. To prove that our greedy solution, A, is optimal, we must show that A contains the same number of intervals as an optimal solution, O. We then can compare partial solutions, showing that A is doing better in a step-by-step fashion.

Interval Scheduling Algorithm:

Sort jobs by finish times so that f1 ≤ f2 ≤ ... ≤ fn
G = {}
for j = 1 to n
    if job j compatible with G
        G = G ∪ {j}
return G

This algorithm runs in O(nlogn) time because we first sort the request, taking O(nlogn), then we construct an array in O(n) time, and we do one pass through n intervals, spending constant time per interval, which takes O(n) time. So, overall we can say the algorithm is O(nlogn).

A similar problem is the Interval Partitioning Problem in which we must partition all intervals across multiple resources (ex. scheduling classes in classrooms). In any instance of Interval Partitioning, the number of resources is going to be at least the depth of the set of intervals.

Interval Partitioning Algorithm:

Sort intervals by starting time so that s1 ≤ s2 ≤ ... ≤ sn
d = 0
for j = 1 to n
    if lecture j is compatible with some classroom k
        schedule lecture j in classroom k
    else
        allocate a new classroom d + 1
        schedule lecture j in classroom d + 1
        d = d + 1

This algorithm runs in O(nlogn) time because for each classroom k, we maintain the finish time of the last job added, and we can keep the classrooms in a priority queue by the last job's finish time.