Course: 113-1 Introduction to Algorithms. Lecturer: Huilan Chang. 2024.12.15 Reference: 16.1 An Activity-selection Problem (Introduction to Algorithms, 3e, by Cormen, Leiserson, Rivest, Stein)

Preliminaries

<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.

  ① with the least duration. ② with the least overlap. (overlaps the fewest other remaining activities) ③ with minimum $f_i$. (最早結束) ④ with maximum $s_i$. (最晚開始) Which of them would work?