I believe the problem can be reduced to sorting
Speaking of which: Given values 0 < a_i < A for some A, apply the skyline algorithm to the rectangles a_i < x < A, 0 < y < a_i. The resulting sequence of heights gives you the values a_i sorted in increasing order; thus the skyline problem cannot be solved in less than O(n log n) time.
The problem becomes much more interesting when you consider optimal parallel performance. The best span you can do is log^2 n. I believe the problem can be reduced to sorting, though it is not required to explicitly sort the sequence of buildings in order to achieve the desired asymptotic performance.