04greedy算法设计与分析 贪心算法(7)

Interval Scheduling: AnalysisTheorem. Greedy algorithm is optimal. Pf. (by contradiction) Assume greedy is not optimal, and let's see what happens. Let i1, i2, ... ik denote set of jobs selected by greedy. Let j1, j2, ... jm denote set of jobs in the optimal solution with i1 = j1, i2 = j2, ..., ir = jr for the largest possible value of r.

job ir+1 finishes before jr+1

Greedy:

i1

i2

ir

ir+1

OPT:

j1

j2

jr

jr+1why not replace job jr+1 with job ir+1?

...

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库04greedy算法设计与分析 贪心算法(7)在线全文阅读。