Class Code: AMC621 Instructor: Huilan Chang
**Reference: 16.1 An Activity-selection Problem (Introduction to Algorithms, 3e, by Cormen, Leiserson, Rivest, Stein)
<aside>
A greedy algorithm 貪心演算法 always makes the choice that looks best at the moment. It makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution.
</aside>
▪️Dynamic programming considers "all possible ways" to derive an optimal solution. 特點：DP考量全局。It uses tables to avoid re-computing solutions of sub-problems.
▪️For many optimization problems, the greedy strategy is sufficient to drive an optimal solution (not necessary to use dynamic programming)
Ex. The activity-selection problem, the fractional Knapsack problem, Minimum spanning trees, Huffman code…
The Activity-selection Problem
Definition. Let $S=\{a_1, a_2,..., a_n\}$ be a set of $n$ activities. The activity $a_i$ has a start time $s_i$ and a finish time $f_i$, where $0\leq s_i<f_i<\infty$. Activities $a_i$ and $a_j$ are compatible if $s_i\geq f_j$ or $s_j\geq f_i$. 圖示：
▪️The activity-selection problem is to select a maximum number of mutually compatible activities. Example.
▪️Consider the following greedy choices: Every time, choose an activity satisfying (•) and compatible to the chosen activities.
(1) with the least duration. (2) with the least overlap. (overlaps the fewest other remaining activities) (3) with minimum $f_i$. (最早結束) (4) with maximum $s_i$. (最晚開始) Which of them would work?