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

Interval Partitioning: Lower Bound on Optimal SolutionDef. The depth of a set of open intervals is the maximum number that contain any given time. Key observation. Number of classrooms needed depth. Ex: Depth of schedule below = 3 schedule below is optimal.a, b, c all contain 9:30

Q. Does there always exist a schedule equal to depth of intervals?

3 2 1

c b a9 9:30 10 10:30 11

d

f g e h1 1:30 2 2:30 3 3:30

j

i

11:30

12

12:30

4

4:30

Time12

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