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 4 classrooms to schedule 10 lectures.
4
e c b a9 9:30 10 10:30 11 11:30 12 12:30 1 1:30
j g h f2 2:3
0 3 3:30
3 2 1
d
i4 4:30
Time10