Skyline of Buildings

Question

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)?

Answer 1

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

Answer 2

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

Answer 3

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 

Answer 4

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;
}