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