Interval Coloring Problem Consider the following: INPUT: A set S = {(, )|1 } of intervals over the real line. Think of interval (Xi, Yi) as being a request for a room for a class that meets from time Xi to time Yi. OUTPUT: Find an assignment of classes to rooms that uses the fewest number of rooms. Note that every room request must be honored and that no two classes can use a room at the same time. (a) Consider the following iterative algorithm. Assign as many classes as possible to the first room (we can do this using the greedy algorithm discussed in class, and in the class notes), then assigns many classes as possible to the second room, then assign as many classes as possible to the third room, etc. Does this algorithm solve the Interval

Coloring Problem? Justify your answer.

(b) Consider the following algorithm. Process the classes in increasing order of start times. Assume that you are processing class C. If there is a room R such that R has been assigned to an earlier class, and C can be assigned to R without overlapping previously assigned classes, then assign C to R. Otherwise, put C in a new room. Does this algorithm solve the Interval Coloring Problem? Justify your answer.

HINT: Lets be the maximum number of intervals that overlap at one particular point in time. Obviously, you need at least s rooms. Therefore any algorithm that uses only s rooms is obviously optimal. This lower bound on the number of rooms required allows you to prove optimality.