Chapter 4

This chapter, as its descriptive title indicates, talks about greedy algorithm. The introduction of the chapter first points out the philosophy behind the different greedy algorithms: using a local decision to optimal small steps and constructing a overall optimal solution at the same time. Then the introduction summarizes the context of the chapter: listing out examples to let us get a feeling of why greedy algorithms are greedy.

This section illustrates the first example of greedy algorithms in details: the interval scheduling. The core inside this algorithm is to find out the criterion of being greedy to rule each small step. There are three seemingly appealing criterions that do not work: earliest starting time, smallest interval of time, and most compatible. We did not manage to come up with a counter example in class to disapprove the most compatible case. The book gives a neat example, so that is good. The actual working criterion is the earliest finishing time.