Skyline of Buildings

912 views Asked by At

I'm trying to understand the skyline problem. Given n rectangular building and we need to compute the skyline. I have trouble in understanding the output for this problem.

Input: (1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28) }

Output Skylines: (1, 11), (3, 13), (9, 0), (12, 7), (16, 3), (19, 18), (22, 3), (25, 0)

The output is pair (xaxis, height). Why is the third pair (9,0)? If we see the skyline graph, the x-axis value 9 has height of 13, not 0. Why is it showing 0? In other words, if we take the first building (input (1,11,5)), the output is (1, 11), (5, 0). Can you guys explain why it is (5,0) instead of (5,11)?

4

There are 4 answers

0
Zhan On

using the sweep line algorithm; here is my python version solution:

class Solution:
    # @param {integer[][]} buildings
    # @return {integer[][]}
    def getSkyline(self, buildings):
        if len(buildings)==0: return []
        if len(buildings)==1: return [[buildings[0][0], buildings[0][2]], [buildings[0][1], 0]]

        points=[]
        for building in buildings:
            points+=[[building[0],building[2]]]
            points+=[[building[1],-building[2]]]
        points=sorted(points, key=lambda x: x[0])

        moving, active, res, current=0, [0], [],-1

        while moving<len(points):
            i=moving
            while i<=len(points):
                if i<len(points) and points[i][0]==points[moving][0]:
                    if points[i][1]>0:
                        active+=[points[i][1]]
                        if points[i][1]>current:
                            current=points[i][1]
                            if len(res)>0 and res[-1][0]==points[i][0]: 
                                res[-1][1]=current
                            else:
                                res+=[[points[moving][0], current]]
                    else:
                        active.remove(-points[i][1])
                    i+=1
                else:
                    break

            if max(active)<current:
                current=max(active)
                res+=[[points[moving][0], current]] 
            moving=i
        return res 
0
Jordi Vermeulen On

Your output does not signify "at x the height is y", but rather "at x the height changes to y".

0
David Eisenstat On

Think of the rooftop intervals as closed on the left and open on the right.

0
kumar On
static long largestRectangle(int[] h) {

    int k=1;
    int n=h.length;
    long max=0;

    while(k<=n){

        long area=0;
        for(int i=0;i<n-k+1;i++){
            long min=Long.MAX_VALUE;
            
            for(int j=i;j<i+k;j++){

                //System.out.print(h[j]+" ");
                min=Math.min(h[j],min);
            }
           // System.out.println();
            area=k*min;
            //System.out.println(area);
            max=Math.max(area,max);
        }
        //System.out.println(k);
        k++;
    }
    return max;
}