Interval Partitioning

Goal: Lecture $j$ starts at $s_j$ and finishes at $f_j$. Find minimum number of classrooms to schedule all the lectures so no two lectures occur at the same time in the same room

Algorithm: Sort lectures in ascending order of start time. Iterate over those lectures. If the lecture is compatible with an existing classroom, assign it to that classroom. If not, open a new classroom.

Time Complexity: $O(n\log n)$ due to sorting

Definition (Depth)

The depth of a set of intervals is the maximum number of intervals that contain any given point.

Observations

• The number of classrooms must be at least the depth
• The earliest-start-time first algorithm never schedules two incompatible lectures in the same classroom

Theorem

Earliest-start-time-first algorithm is optimal

Proof:

• Let $d=$ number of classroom that the algorithm allocates
• Classroom $d$ is opened because we needed to schedule a lecture, say $lj$ that is incompatible with a lecture in each of $d-1$ other classrooms.
• Thus, these $d$ lectures each end after $s_j$.
• Since we sorted by start time, each of these incompatible lectures start no later than $s_j$.
• Therefore, $d$ is the depth of the set.
• All schedules must use at least $d$ classrooms, so using $d$ classrooms is optimal. $\square$