交大110 資料結構與演算法第27題｜演算法 Ch7 貪婪演算法

演算法›Ch7 貪婪演算法

第 5 題／共 12 題

5. Activity Selection、Greedy Algorithm

#AL-07-005中Activity SelectionGreedy Algorithm

Activity-selection problem. Suppose we have a set $S=\{a_1,a_2,\ldots,a_n\}$ of n proposed activities. Each activity $a_i$ has a start time $s_i$ and a finish time $f_i$ , where $0\le s_i < f_i < \infty$ . If selected, activity $a_i$ takes place during the half-open time interval $[s_i,f_i)$ . Activities $a_i$ and $a_j$ are compatible if the intervals $[s_i,f_i)$ and $[s_j,f_j)$ do not overlap. That is, $a_i$ and $a_j$ are compatible if $s_i\ge f_j$ or $s_j\ge f_i$ . In the activity-selection problem, we wish to select a maximum-size subset of mutually compatible activities. For the following greedy ideas, select the one(s) that yield an optimal solution.

📄 交大110

▤完整推導請見《WH 資工筆記 · 演算法》Ch7 貪婪演算法

本章題號 · 1–12 / 12