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

Interval Partitioning: Greedy AnalysisObservation. Greedy algorithm never schedules two incompatible lectures in the same classroom. Theorem. Greedy algorithm is optimal. Pf. Let d = number of classrooms that the greedy algorithm allocates. Classroom d is opened because we needed to schedule a job, say j, that is incompatible with all d-1 other classrooms. These d jobs each end after sj. Since we sorted by start time, all these incompatibilities are caused by lectures that start no later than sj. Thus, we have d lectures overlapping at time sj + . Key observation all schedules use d classrooms.

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