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

Interval Partitioning: Greedy AlgorithmGreedy algorithm. Consider lectures in increasing order of start time: assign lecture to any compatible classroom.Sort intervals by starting time so that s1 s2 ... sn. d 0 number of allocated classrooms for j = 1 to n if (lecture schedule else allocate schedule d d + } { j is compatible with some classroom k) lecture j in classroom k a new classroom d + 1 lecture j in classroom d + 1 1

Implementation. O(n log n). For each classroom k, maintain the finish time of the last job added. Keep the classrooms in a priority queue.

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