Interval Partitioning

Input A set of intervals, ${1,2,...,n}$ with start time $s(i)$ and finish time $f(i)$.

Output All intervals scheduled using the fewest possible resources.

The number of resources needed is at least the depth of the set of intervals. The depth is given by the maximum number of intervals which pass over a single point in time. Therefore the optimal solution will at least as many resources as the depth.

The algorithm for interval partitioning is as follows:

sort intervals by start time
for each interval
    if interval is compatible with an existing resource
        add it to the existing resource
    else
        create a new resource
        add it to the new resource