Find the key points of the outer layer of n overlapping rectangles – Divide and Conquer


Given a set of $ n$ rectangles depicted as: $ [Li, Ri, Hi]$ whereby the corners of the $ i-th$ rectangle are – $ (Li, 0), (Ri,0), (Li, Hi)$ and $ (Ri, Hi)$ .

The goal is to print all of the key points of the outer layer of the $ n$ overlapping rectangles (given in a list).

Key points $ (Xj, Yj)$ are the points that collectively portray the outer layer of the rectangles – look at the example below:

Given the two blocks [4, 13, 4] and [2, 7, 10] the output should be: [2,0], [2,10], [7,10], [7,4], [13,4] and [13,0] (The points that are marked red).

This should be done in $ O(nlogn)$ time where $ n$ is the number of buildings (rectangles).

enter image description here

I have tried to solve this problem by –

(1) Sorting the blocks by priority: $ Li$ then $ Ri$ then $ Hi$ .

(2) Compare any two blocks: $ [Li, Ri, Hi]$ and $ [Li+1, Ri+1, Hi+1]$ (15 different cases like Li==Li+1 and Hi< Hi+1 and stuff like this).

(3) Remove/add points according to condition (using AVL)

This works in some cases, but in others it fails miserably. I think this can be solved by Convex Hull algorithms, we have only learned the divide and conquer method so far – but I cannot link between this question and this method. I hope you can help me with this one!

Thank you