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 = {[a₁, b₁], [a₂, b₂],..., [a_n, b_n]} of subintervals 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 interval [a_i, b_i] in S. The skyline of S is defined to be a list of pairs [(x₀, c₀),(x₁, c₁),(x₂, c₂),...,(x_m, c_m),(x_m+1, 0)], with x₀ = 0 and x_m+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 [x_i, x_i+1], for i = 0, 1,...,m. Design an O(n log n)- time algorithm for computing the skyline of S.