title: Merge skylines, divide and conquer
body: <p>I'm trying to solve the famous skyline problem (see gif):</p>
  
  <p><img src="https://i.imgur.com/SnSjn.gif" />
  Input </p>
  
  <blockquote>
    <p>(1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28)</p>
  </blockquote>
  
  <p>Should return, the points that are behind other buildings should be gone and the coordinates of changes in the Y-axis should be in the returning skyline:</p>
  
  <blockquote>
    <p>(1, 11), (3, 13), (9, 0), (12, 7), (16, 3), (19, 18), (22, 3), (23, 13), (29, 0)</p>
  </blockquote>
  
  <p>I'm trying to do so by using a divide and conquer approach to the algorithm as to achieve a running time of O(n lg n), but I'm stuck on the merge part.</p>
  
  <p>Everytime I think about it I get confused. For example,  I check which one the skylines is first e.g. which has the lower x-coordinate, then I add that + its hight to my new skyline. But then I encounter a skyline thats behind two other skylines, how can I detect this 'collision'? </p>
  
  <p>Do I first check if the skylines have any overlap by checking if left.x2 &lt; right.x1? But then I think what should I check first? Overlap of precedence on the x-axis and everything turns into a big chicken-egg mess. </p>
  
  <p>Maybe I'm thinking too complicated? What I need is the set of highest y coordinates, at every intersection, should I approach it like this? </p>