\documentclass{article}
\input{6046preamble}


\begin{document}
\pset{7-3}{Dan Ports}{No collab}{Recitation \#8}

\begin{ppart}{Algorithm}
For this algorithm, we will also use a sweep-line approach. Essentially, as we sweep the line from left to right, we will keep track of the y-coordinates of all the ``active'' rectangles, and multiply the largest y-coordinate by the change in x-coordinate to determine the area to be added.
\paragraph{}
Specifically, given our input arrays $x_1[1\ldots n]$, $x_2[1\ldots n]$, and $y_1[1 \ldots n]$, we will begin by combining them into one array $A[1\ldots n]$ containing all information for each rectangle, such that $A[i].\mathit{left}=x_1[i]$, $A[i].\mathit{right}=x_2[i]$, and $A[i].\mathit{top}=y[i]$. Assembling this array requires iterating through the other three arrays, in $\Theta(n)$ time. We next assemble an array $B[1\ldots2n]$ containing all x-coordinates of interest ($A[i].\mathit{left}$ and $A[i].\mathit{right}$ for every $i$) and a pointer to the associated element of array $A$. Assembling this array requires $\Theta(n)$ time, and we next sort it in increasing order by x-coordinate, requiring $\Theta(n \lg n)$ time.
\paragraph{}
Next we initialize a loop variable $i \leftarrow 1$, a counter $R \leftarrow 0$ in which we will accumulate our result, and a balanced BST $T$ in which we will store the y-coordinates of all active rectangles. We iterate from $i=1$ to $i=2n$. On each iteration of the loop except the first ($i > 1$), we calculate the area required to paint the previous section of rectangles. This is calculated by taking the difference in x-coordinates between $B[i]$ and $B[i-1]$, and multiplying it by the maximum y-value contained in $T$ (or zero if $T$ is empty). We add that value to $R$. Then, if $B[i]$ points to the left coordinate of a rectangle, we follow the pointer and add the y-coordinate of that rectangle to $T$. Otherwise, if $B[i]$ points to the right coordinate of a rectangle, we follow the pointer and remove the y-coordinate of that rectangle from $T$. Once we have completed all $2n$ iterations of this loop, we return the result contained in $R$.
\end{ppart}

\begin{ppart}{Runtime analysis}
Generating the arrays $A$ and $B$ requires $\Theta(n)$ time, as shown above. Sorting $B$ requires $\Theta(n \lg n)$ time. Each iteration of the loop requires finding the maximum element of $T$, and either adding an element to or removing an element from $T$, each of which can be done in $O(\lg n)$ time. The loop is run $2n = \Theta(n)$ times, so running the loop requires $O(n \lg n)$ time. The algorithm is thus overall $\Theta(n \lg n)$.
\end{ppart}

\begin{ppart}{Proof of correctness}
To prove correctness, we justify the claim that the total area required to paint the rectangles is the sum on $i$ of the product between the distance between the points $B[i]$ and $B[i-1]$ and the maximum y-coordinate of a rectangle that starts at x-coordinate $B[i-1]$ or to the left and at x-coordinate $B[i]$ or to the right. Given a shape of overlapping rectangles, we can certainly divide it into many different rectangles without changing the area by splitting it at each of the ``points of interest'' listed in the array $B$. Then we have a number of rectangles, each of which has its left edge at the x-coordinate $B[i-1]$ and its right edge at $B[i]$ for some $i$. Thus for any fixed $i$, we can find a set $E$ of rectangles which have left edge at $B[i-1]$ and right edge at $B[i]$. There must be some rectangle $E_{max}$ which has the largest y-coordinate. Then every other rectangle in $E$ is contained within $E_{max}$ and can effectively be discarded. Applying this for every $i$, we see that the algorithm's approach of summing the product of the length of the interval $(B[i-1],B[i])$ and the largest y-coordinate of a rectangle that contains this interval is valid.
\paragraph{}
Finally, we note that it is easy to show that the algorithm correctly determines the aforementioned sum of products. This can be done by using an invariant: the tree $T$ contains the y-coordinates of all rectangles that start at or before the x-coordinate $B[i-1]$ and end at $B[i]$ or after. Clearly the algorithm maintains this invariant by adding and deleting points in the tree whenever it encounters the left or right sides of a rectangle. Using this invariant, we know that taking the maximum y-coordinate contained in $T$ and multiplying by the length of the interval gives the correct amount of paint required for the interval $(B[i-1],B[i])$. Thus the sum on $i$ of this quantity is the total amount of paint required, and the algorithm gives the correct result. 
\end{ppart}
\end{document}