Why not just sort the rectangles by the left side position, then walk through the list, drawing a line from the current position to either the right of the next rectangle (in case that one is taller) or to the right of the current rectangle, in case it is not?

This even makes it easy to parallize it because you can use the quick sort algorithm to split the rectangles in two non-overlapping sets and once your two cores have made the two parts of the skyline you only need to update the line between them.