$(20$ points$)$ You are given a set of rectangles $S=\{R_1,R_2,$dots,$R_n\}$ such that all have their bottom sides on the $x-$axis. This means that each rectangle $R_i$ is specified by a triple $(l_i,r_i,h_i),$ where $l_i$ and $r_i$ are the $x$ coordinates of its left and right sides, and $h_i$ is the height. For simplicity, you may assume that all $l_i,r_i,h_i$ for $i=1,$dots,$n$ are distinct.

You will design an algorithm to compute the union $C=R_1{R}_2$cdots$R_n.$ Clearly, the bottom side of $C$ is a straight line segment from the leftmost lower$-$left corner $u$ of $R_1,$dots,$R_n$ to the rightmost lower$-$right corner $v$ of $R_1,$dots,$R_n.$ So you only need to find its upper boundary $.$ Your algorithm should output $$ as a list of "key points" sorted by their $x$ coordinate in the form $((x_1,y_1),(x_2,y_2),$dots$).$ Each key point is the left endpoint of some horizontal segment in $$ except the last point in the list, which always has a y$-$coordinate $0$ and is used to mark the termination.

The following figure shows an example, where the input is

$((2,9,10),(3,7,15),(5,12,12),(15,20,10),(19,24,8)),$

and the output should be

$((2,10),(3,15),(7,12),(12,0),(15,10),(20,8),(24,0)).$

$3$

Design an algorithm that constructs $$ in $O(nlogn)$ time and analyze its running time. Your algorithm MUST use the following divide$-$andconquer strategy:

$($i$)$ Recursively solve the subproblems for $R_1,$dots,$R_{\frac{n}{2}}$ and $R_{\frac{n}{2}+1},$dots,$R_n,$ respectively. Note that there is no particular ordering among $R_1,R_2,$dots,$R_n$ in the input.

$($ii$)$ Let ${}_1$ and ${}_2$ be the outputs of the two recursive calls in $($i$).$

$($iii$)$ Combine ${}_1$ and ${}_2$ to produce $.$