Figuring Algo for assignment

Hey all, I just received my next assigment frommy data structures and discrete math class; I have a hunch on how to do it but I can't think of the base case...anyways here is roughly what I have to do:

Title: Skyline problem
There is a city with no hills and has a set of rectangular buildings. Suppose you are viewing the city from water. Leftmost position of city is used as reference point ( horiz position 0 ). This, a building can be speified by (l, h, w), where l gives the left boundary, h the height of the buildingsm and w its width.

the program will take as input a set of n buildings, in no particular order. The program now has to extract the outline formed by the buildings. This skyline will be formed by a sequence of horizontal segments starting at position 0. It will be represented by a equence of pairs (h, w) where h is the height abd w the width.

Code:

So basically if the input from a file is:
(13, 3 4), (3,6,6,), (1,2,9), (14, 2,5), (18,4,2)
the corresponding output will be:
(0,1), (2,2), (6,6), (2,1),(0,3),(3,4),(2,1),(4,2)

there are some restirictions for the design: must use divide and conquer algorithm and must be linear time operation.

I hope you guys understand what the qestion is asking for, i tried to "draw" a picture of what it supposed to be

Code:

           __________
          |          |
      ____|_____     |
     |          |    |       ______
 ____|__________|____|______|______|
0    a    b          c      d      e
   
        
           __________ 

      ____          
                             ______
 ____ __________ ____ ______ ______ 
0    a    b          c      d      e
where all the red pieces would correspond to the output sequence of pairs (hi, wi)

since it is a D&C algo, I was thinking of using a similar algo to merge sort, where I would break the n buildings into two groups of roughly equal size, and then recursively find the skyline of each group.

The problem is that I'm not sure how it will work for a base case, ie. if the is only one building.

any comments? suggestions on how to go about it?

So is the program supposed to draw the skyline using ascii art (ie. with "-" and "|")?
And by "command and conquer" do you mean divide and conquer?

gg

Hmmm... never thought of doing this as divide and conquer. I did this not too long ago by simply having an array that corresponded to each horizonatal point in the city and the value of each point corresponded to the height at that point initialized to zero, so the code looked something like this:

Code:

loop through each building
   for (x=beg position of building to ending position of building)
       if (height of building is greater than citypos[x])
            citypos[x]=height of building

But I guess worst case scenario this wouldn't be considered linear.

For D&C, I would probably have a function that merged two city lines, so if it was given

Code:

 (0,1),(2,2),(0,6) and (0,2),(3,3),(0,4)

it would return

Code:

(0,1),(2,1),(3,3),(0,4)

and also have a function that returns the skyline for a single building, then your recursive function would look something like this:

Code:

string recursiveFunc(int start, int size)
{
// start is beginning of array of buildings passed to function and size is size the array
if (size==1)
    return singleBuildingSkyline(Buildings[start]);
else
    return mergeSkyline(recursiveFunc(start, size/2),recursiveFunc(start+size/2, size/2));
}

There might be some flaws with that and you'll have to account for round off errors, haven't thought it all the way through, but hopefully you get the idea.

Originally posted by Codeplug
So is the program supposed to draw the skyline using ascii art (ie. with "-" and "|")?
And by "command and conquer" do you mean divide and conquer?

gg

No, no, the program is not supposed to draw it, just output the segments' heights and widths.

and yes, i did mean divide and conquer...lol...sorry

PJYelton: thanks a lot,thats exactly what I was thinking (recursive example)...I just couldn't bring it down to the single building for some reason. I'll start coding the program shortly.

One more question though; since the input is obtained from a text filewill it be mroe beneficial to store it into an array or a linked list? what would be the pros and cons of both?