Consider the "Shortest Interval first" greedy algorithm for the Interval Scheduling problem. In this algorithm, we repeatedly pick a shortest interval to include in our solution and as usual when an interval I am picked, then I and any overlapping intervals still present are deleted. The algorithm breaks ties arbitrarily; in other words, if there are multiple shortest intervals present, the algorithms picks one arbitrarily. (a) Show that this algorithm does not solve the Interval Scheduling problem. In other words, even though the algorithm returns a non-overlapping set of intervals, the set it returns need not be the largest possible set. (We have discussed a counterexample for this algorithm in class.) (b) Let A be the set of intervals returned by the algorithm for some input and let O be an optimal solution for this input. Prove that every interval in A overlaps at most two intervals in O. (c) Consider an arbitrary input and let A be the set of intervals returned by the algorithm for this input and let O be an optimal solution for this input. Now for each interval x in O, charge $1 to an interval y in A that overlaps x. Note that y could be identical to x. Also, note that y has to exist; otherwise the greedy algorithm would have added x to the set A. Thus the number of dollars charged is exactly equal to |0|. Now answer the following questions: (i) what is the maximum number of dollars that an interval in A is charged? (ii) what does this tell us about the relative sizes of A and O? (Express your answer as an inequality connecting |/1| and |0|.), and (iii) what does this tell us about the "shortest interval first" algorithm being an approximation algorithm for Interval Scheduling