if we think about it somewhat, it becomes apparent, that it would take linear time to merge one building to the skyline, and also two skylines together.

merging skylines together gets us more bang-for-the-buck. and is trivially done with scanning them from left->right, match x-coordinates, adjust heights...

all of this is just divide-and-conquer, and usual recurrence rules apply i.e. T(n) = 2T(n/2)+O(n), which means T(n) = O(n lg n)