Scheduling Classes

The next example is slightly more complex. Suppose we decide to drop out of computer science and change our major to Applied Chaos. The Applied Chaos department offers all of its classes on the same day every week, called “Soberday” by the students (but interestingly, not by the faculty). Every class has a different start time and a different ending time: AC 101 (“Toilet Paper Landscape Architecture”) starts at 10:27pm and ends at 11:51pm; AC 666 (“Immanentizing the Eschaton”) starts at 4:18pm and ends at 4:22pm, and so on. In the interest of graduating as quickly as possible, we want to register for as many classes as possible. (Applied Chaos classes don’t require any actual work.) The university’s registration computer won’t let us register for overlapping classes, and no one in the department knows how to override this “feature.” Which classes should we take?

Finding the largest non-overlapping subset of rectangles: a problem of scheduling classes

More formally, suppose we’re given two arrays $S[1 .. n]$ and $F [1 .. n]$ listing the start and finish times of each class; to be concrete, we can assume that $0 ≤ S[i] < F[i] ≤ M$ for each $i$, for some value $M$ (for example, the number of picoseconds in Soberday). Our task is to choose the largest possible subset $X ∈ {1,2,...,n}$ so that for any pair $i, j ∈ X$, either $S[i] > F[j]$ or $S[j] > F[i]$. We can illustrate the problem by drawing each class as a rectangle whose left and right x-coordinates show the start and finish times. The goal is to find the largest subset of rectangles that doesn’t overlap vertically.