title: Find the key points of the outer layer of n overlapping rectangles - Divide and Conquer
body: <p>Given a set of <em>n</em> rectangles depicted as: <em>[Li, Ri, Hi]</em> whereby the corners of the <em>i-th</em> rectangle are - <em>(Li, 0), (Ri,0), (Li, Hi)</em> and <em>(Ri, Hi)</em>.</p>
  
  <p>The goal is to print all of the <strong>key points</strong> of the outer layer of the n overlapping rectangles (given in a list).</p>
  
  <p><strong>Key points</strong> (Xj, Yj) are the points that collectively portray the outer layer of the rectangles - look at the example below:</p>
  
  <p>Given the two blocks [4, 13, 4] and [2, 7, 10] the <strong>output</strong> should be: [2,0], [2,10],  [7,10],  [7,4], [13,4] and [13,0]  (The points that are marked red).</p>
  
  <p>This should be done in O(nlogn) time where n is the number of buildings (rectangles).</p>
  
  <p><a href="https://i.stack.imgur.com/6cDEi.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/6cDEi.png" alt="enter image description here"></a></p>
  
  <p>I have tried to solve this problem by -</p>
  
  <p>(1) Sorting the blocks by priority: Li then Ri then Hi.</p>
  
  <p>(2) Compare any two blocks: [Li, Ri, Hi] and [Li+1, Ri+1, Hi+1] (15 different cases like Li==Li+1 and Hi&lt; Hi+1 and stuff like this).</p>
  
  <p>(3) Remove/add points according to condition (using AVL)</p>
  
  <p>This works in some cases, but in others it fails miserably. </p>
  
  <p>I am not asking for a code - a pseudo code or an explanation/algorithm would be best :)
  I hope you can help me with this one!</p>
  
  <p>Thank you</p>