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

Interval Scheduling: Greedy AlgorithmGreedy algorithm. Consider jobs in increasing order of finish time. Take each job provided it's compatible with the ones already taken.

Sort jobs by finish times so that f1 f2 ... fn.set of jobs selected

A for j = 1 to n { if (job j compatible with A) A A {j} } return A

Implementation. O(n log n). Remember job j* that was added last to A. Job j is compatible with A if sj fj*.

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