For small integers, just draw them on a bitmap and walk along the boundary.

Other than that, a tree or skip list where inserting a rectangle can split a node in two so that given an initial SkyLine(height, min_x, max_x) of (0, min, max) then adding (8, 10, 20) you get [(0,min,10),(8,10,20),(0,20,max)] as leaf elements.