(a) In pseudo-code, give a greedy algorithm that computes the minimum cover Ymin in O(n log n) time. Justify your answer. (Hint: Starting with the left-most tile.) (b) Prove that your algorithm (i) covers each component and (ii) produces the min- imal cover for each component. Explain why these conditions are necessary and sucient for the correctness of the algorithm.

5. Professor Dumbledore hands you a set X of n 0 intervals on the real line and asks you to find a subset of these intervals Y C X, called a tiling cover, where the intervals in Y cover the intervals in X, that is, every real value contained within some interval in X is also contained in some interval Y. he size of a tiling cover is just the number of intervals IYI. To satisfy Dumbledore, you must return the minimum cover Ymin: the tiling cover with the smallest possible size. For the following, assume that Dumbledore gives you an input consisting of two arrays XLI1...nj and XR[1...nl, representing the left and right endpoints of the intervals inX