Let X be a set of n intervals on the real line. A proper coloring of X assigns a color to each interval, so that any two overlapping intervals are assigned different colors. Describe and analyze an efficient algorithm to compute the minimum number of colors needed to properly color X. Assume that your input consists of two arrays L[1..n] and R[1..n], where L[i] and R[i] are the left and right endpoints of the ith interval The motivation for this problem is similar to the motivation for the Interval Scheduling problem we studied in class. Suppose that we are given a bunch of events (e.g., courses) we need to schedule, then finding the fewest number of rooms we can schedule all of these events in, is the Interval Coloring problem described here. Here is a brief description of a greedy algorithm, you should consider. Let P-11,2,3,...) be the set of "colors" we want to use for the interevals. Consider the intervals one-by-one in left-to-right order of start times and to each interval, assign the smallest color from P that is "available." You'll have to think pretty carefully about how to prove the correctness of this algorithm and how to present your proof. Your proof will be graded for correctness as well as clarity.
