Q$3.$ A segment of a vertical line is the collection of points between a starting point and an

ending point on the line, including the starting and ending points. We write

$[$ystart$,$yend$]$ for the segment whose starting and ending y$-$coordinates are ystart and

yend, respectively. It is always the case that ystart $<$ yend. Two segments are called

overlapping when they share at least one point, and non$-$overlapping otherwise.

The following Abstract Data Type $($ADT$)$ stores non$-$overlapping segments which lie on

the same line:

public class SegmentsST

SegmentsST$()$ Creates an empty SegmentsST object.

public void insert$($int start, int end$)$ Inserts the segment $[$start$,$ end$]$ in the

ADT.

public void delete$($int start, int end$)$ Deletes any segment in the ADT that

overlaps with $[$start$,$ end$].$ You may

assume that at most one segment will

overlap with $[$start$,$ end$].$

public boolean overlaps$($int start, intend$)|$ Returns true if the ADT contains at

least one segment overlapping with

$[$start$,$ end$],$ and false otherwise.

Implement the above ADT in Java so that the three methods have the most efficient

worst$-$case asymptotic running time. You should justify your answer.

In your implementation you can use any of the standard generic ADTs:

Stack MaxPriorityQueue$>$

MinPriorityQueue$>$

SymbolTable, Value$>$

UndirectedGraph DirectedGraph

Where Comparable is the following generic Java interface:

public interface Comparable

int compareTo$($T o$)$ Compares this object with the specified object o$.$ It returns

a negative number if $$this is less than o$,$ a positive

number if $$this is greater than $0,$ and zero if $$this is equal

too$.$

You do not need to implement the ADTs you use, however for each one you use you

should specify:

$$ An APJ of the ADT, similar to the one given above for SegmentsST. The API only

needs to contain the methods you use in your implementation.

$*$ Atight upper bound of the worst$-$case asymptotic running time of each of the ADT

methods.

e A known implementation of the ADT that has the running time properties you

specified above.

An axis$-$aligned rectangle is the collection of points enclosed in sides that are either

parallel or perpendicular to the y$-$axis $($including the points on their sides$).$ Axis$-$

aligned rectangles are represented by the x$-$ and y$-$coordinates of two points: the

upper left corner and bottom right corner. Two rectangles are called overlapping if

they share at least one point.

y$-$axis

$($ulx$,$ uly$)$

$($brx$,$ bry$)$

x$-$axis

You may assume that it is always the case that ulx $<$ brx and bry $<$ uly.

We encode axis$-$aligned rectangles as objects of the class:

public class Rectangle $\{$

public int ulx; public int uly; public int brx; public int bry;

Rectangle$($int ulx, int uly, int brx$,$ int bry$)\{$

this.ulx $=$ ulx; this.uly $=$ uly; this.brx $=$ brx; this.bry $=$ bry;

$1$

$$ Give an efficient Java implementation of the method:

public boolean containsOverlaps$($Rectangle$[]$ rs$)$

Which takes an array of Rectangle objects $($in no particular order$)$ and it returns

true if there are any overlapping rectangles in the array, otherwise false.

$*$ Give a English description of your implementation and its worst$-$case running time.

Your implementation can define auxiliary classes and methods. Additionally, you can

use the SegmentsST ADT and the generic heapsort method:

public static void heapsort$($Comparabie$[]$ pq$)$