Consider the following greedy algorithm for the interval scheduling problem: Pick an interval I with minimum length, remove I and all intervals that overlap with I, and repeat this process until no more intervals remain. The pseudocode for the algorithm is described as follows (Note: S is the set of input intervals):

Set R to S, and 0 to the empty set.

While R is not empty {

Let i be an interval in R with minimum length. (Break ties arbitrarily)

Add i to 0.

Remove from R interval i and all intervals that conflict with i.

} endwhile

Return 0.

A. Give an example that shows this algorithm does not always return an optimal solution. (10 points) B. Is it true that on every input instance the solution returned by the algorithm has a size that is at least half the size of an optimal solution? Provide an argument supporting your answer. (20 points)