Interval PartitioningInterval partitioning. Lecture j starts at sj and finishes at fj. Goal: find minimum number of classrooms to schedule all lectures so that no two occur at the same time in the same room.
Ex: This schedule uses only 3.
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
Time11