Divide and Conquer Algorithms: Suppose you have a geometric description of the buildings of Manhattan and you would like to build a representation of the New York skyline. That is, suppose you are given a description of a set of rectangles, all of which have one of their sides on the x-axis, and you would like to build a representation of the union of all these rectangles. Formally, since each rectangle has a side on the x-axis, you can assume that you are given a set, S = {[a1,b1],[a2,b2],...,[an,bn]} of sub-intervals in the interval [0,1], with 0 <= ai < bi <= 1, for i = 1, 2,..., n, such that there is an associated height, hi, for each inteval [ai,bi] in S. The skyline of S is defined to be a list of pairs [(x0,c0),(xi,c1),(x2,c2),...,(xm,cm),(xm+1,0)], with x0 = 0and xm+1=1, and ordered by xi values, such that, each subinterval, [xi,xi+1], is the maximal subinterval that has a single highest interval, which is at height ci, in S, containing [xi,xi+1], for i = 0, 1,..., m. Design an O(n log n)-time algorithm for computing the skyline of S.