Given a set S of rectangles, each of which has a side in common with the x axis and non-negative y values the skyline of S is the line tracing the largest y value from any rectangle in S

The Problem:

Write the method getSkyline() that accepts a rectangle set S and returns the skyline for S. Your method should solve the problem three different ways; each solution should produce the correct answer, but will take differing amounts of time: O(n2), O(n log n) or O(n), where n is the number of rectangles in S. You must implement the "Skyliner" interface which is comprised of the following code:

Blockquote

interface Skyliner { public Building [] getSkyline(AlgorithmPerformace p, Building [] cityscape); }

Blockquote

Any help would be very much appreciated. Thanks to everyone in advance.