[Solved] CS 300- The stanbul skyline problem

CS 300 Data Structures

1 IntroductionThe stanbul skyline problem, often mistakenly called the New York skyline problem, isthe problem of drawing the skyline of a city given a set of buildings of that city. In thishomework you will write a program whose input is a list of the locations and sizes ofbuildings, and whose output is a description of the visible skyline, that is, how the citylooks as an outline, when viewed from a distance. For a real-life version of this problem,go to Vaniky on the Asian side of the Bosphorus, and, as you sip your tea, contemplateon how the skyline will look as the sun sets over the European side.To make things simple, the buildings will be given using just two dimensions, x and y,rather than three, ignoring the depth value. (Think of x as horizontal and y as vertical.)Each building will be a rectangle with its base on the x-axis. Thus, a building can becompletely described by giving the x-coordinates of its left and right sides, and the ycoordinate (or height) of its top side. The input will be read from standard input. The firstline of the input indicates how many buildings there are in the city, and each succeedingline will indicate the x-coordinate of the left side of a building followed by the ycoordinateof the top side of the building, followed by the x-coordinate of the right side ofthe building. The following is an example of a valid input to the program:42 50 1035 20 5530 60 455 75 25Notice that buildings may overlap. For example, the first building, which spans 2 through10 on the x-axis, overlaps the fourth building, which spans 5 through 25 on the x-axis. Ifthe right x-coordinate of a building is the same as the left x-coordinate of anotherbuilding, then the two buildings are considered to be side by side (though their heightsmay differ!)The output of this program should be a description of the skyline of the city. The skylineis the upper outline of the buildings in the city. To be more precise, the skyline is afunction that maps each x-coordinate to the y-coordinate of the tallest building that coversthat x-coordinate. Since all of our buildings are rectangles, this function will be a curveconsisting of horizontal and vertical line segments. Your program should describe theskyline function by listing each x coordinate at which the height of the skyline changes,along with the new coordinate of the skyline at that x. Your program should do this in thedirection of increasing x coordinate (i.e., left to right). For example, the following outputdescribes the skyline of the input above:0 02 505 7525 030 6045 2055 0This output indicates that initially the skyline is at height 0 (which may be different ifthere is a building starting at 0). At x-coordinate 2, the height of the skyline becomes 50.The height remains 50 until x-coordinate 5, at which point (because of the fourthbuilding) it becomes 75. Then, at x-coordinate 25 the height becomes 0, and so forth.The following figure depicts this instance of the problem where the buildings are shownwith rectangles and the skyline is shown with the think outline.

2 The Modified Priority Queue ClassThe first part of this assignment is to implement a class that we will call a ModifiedPriority Queue, (MPQ) that will be useful in computing the skyline of a set of buildings.The MPQ is a simple variation on the priority queue class that we used heaps toimplement. The only difference is that the items that are maintained by a MPQ objectinternally have two components (say value and label), as opposed to just a value that isused to compare the items in a priority queue. The first component is again a value withwhich the items can be compared to each other just as in a priority queue. The other,label, is an identifying number that identifies a specific item in the MPQ. Thus forinstance you can insert an item and either access or delete an item with the maximumvalue component or with a specific identifying number.Your class definition should at least have the following method that could be useful forthe rest of the homework. Constructor Destructor void insert(Comparable value, int label): This methodinserts an item with the given value and label into the MPQ. Comparable Remove(int label): This method removes the value withthis label and returns it. Comparable GetMax( ): This method returns the maximum value that iscurrently stored. (Note that contrary to priority queues, we do not remove thevalue from the MPQ data structure!)2 5 10507525 30 35 45 556020XY Finally, our class must allow us to check if it is empty, using the functionBoolean IsEmpty( ).You will use heaps to implement MPQs. Let us assume that you call the array for theheap as Heap. The tricky part is to maintain a link between a value and a label assigned toit. For this, it will be convenient to have a parallel private array of integers, calledLocation, whose ith entry contains the position in the heap of the item having label i. Thusyou can locate a heap entry with a given label in O(1) time, instead of searching for it inthe heap in O(N) time. At all times, for the valid entries in the heap,Heap[Location[i]].label equals i, and Location[Heap[j].label] equals j. When you movean element around in the heap, you should be careful to change the corresponding valuein Location to contain the new position of the element.3 The Skyline ProgramOnce you have implemented the MPQ Class, you will write the code that computes theskyline of a city. We suggest the following algorithm outline but certainly you arewelcome to come up with your own, but you should employ the MPQ class.1. Read in the descriptions of all of the buildings from a file called input.txt. Theformat will be as given earlier.2. Once you have read all the data in, put all of the x-coordinates of the left and rightsides in a separate array (of size twice the number of buildings) together, and sortthem into ascending order of the x-coordinates using some fast sorting algorithm(you can use heapsort, but you will have to modify it a bit). With each xcoordinate,also keep the identity of the corresponding building in the same array(e.g., the sequence number of the building as you read them in), and which side(left or right) it belongs to.3. Make a left-to-right sweep across the city by examining the x-coordinates in thesorted list in ascending order. During the course of the sweep, the MPQ is used tokeep track of which buildings span the current x coordinate and which of thebuildings has the maximum height. You will have to figure out how to use theMPQ class for this. After each insertion and deletion, check to see if the maximumheight of the buildings in the MPQ has changed. If so, output the x- coordinate thathas just been examined, followed by the new current maximum height to thestandard output.