In this Leetcode The Skyline problem solution A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Given the locations and heights of all the buildings, return the skyline formed by these buildings collectively.

Leetcode The Skyline problem solution


Problem solution in Python.

class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        if not buildings:
            return []
        points = []
        for left, right, height in buildings:
            points.append((left, -height))
            points.append((right, height))
        points = sorted(points, key=lambda x: (x[0], x[1])) # break ties when x coordiantes are equal
        from heapq import heappop, heappush, heapify
        res, pq = [], [float('inf')]
        prev_max_height = 0
        for x, height in points:
            if height < 0:
                heappush(pq, height)
            else:
                pq.remove(-height)
                heapify(pq)
            cur_max_height = pq[0]
            if cur_max_height != prev_max_height:
                if cur_max_height == float('inf'):
                    cur_max_height = 0
                res.append([x, -cur_max_height])
                prev_max_height = cur_max_height
        return res



Problem solution in Java.

class cord{
    int x,y;
    boolean isStart;
    cord(int x,int y,boolean f){
        this.x=x;this.y=y;isStart=f;
    }
}
class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        List<List<Integer>> ans=new ArrayList<>();
        if(buildings.length==0) return ans;
        List<cord> l=new ArrayList<>();
        for(int i[]:buildings){
            cord c=new cord(i[0],i[2],true),c1=new cord(i[1],i[2],false);
            l.add(c);l.add(c1);
        }
        Collections.sort(l,new Comparator<cord>() {
            @Override
            public int compare(cord a,cord b){
                if(a.x!=b.x)    return a.x-b.x;
                else{
                    if(a.isStart && b.isStart) return b.y-a.y;
                    else if(a.isStart!=b.isStart)  return a.isStart?-1:1;
                    else    return a.y-b.y;
                }
            }
        });
        TreeMap<Integer,Integer> m=new TreeMap<>();
        m.put(0,1);
        int prevMax=0;
        for(cord i:l){
            if(i.isStart)  m.put(i.y,m.getOrDefault(i.y,0)+1);
            else{
                int v=m.get(i.y)-1;
                if(v==0)   m.remove(i.y);
                else   m.put(i.y,v);
            }
            int max=m.lastKey();
            if(max!=prevMax){
                List<Integer> t=new ArrayList<>();
                t.add(i.x);t.add(max);
                ans.add(t);
                prevMax=max;
            }
        }
        return ans;
    }
}


Problem solution in C++.

bool cmp(vector<int> &A, vector<int> &B){
    if(A[0]!=B[0])
        return A[0]<B[0];
        else if(A[1]==B[1])
            return B[2]==1; 
    else if(A[2]==0 && B[2]==0)
        return A[1]>B[1];
    else if(A[2]==1 && B[2]==1)
        return A[1]<B[1];
    return true;
}
class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        int n=buildings.size();
        
        vector< vector<int> > A;
        for(int i=0;i<buildings.size();i++){
            A.push_back({buildings[i][0],buildings[i][2],0});
            A.push_back({buildings[i][1],buildings[i][2],1});
        }
        sort(A.begin(),A.end(),cmp);
        multiset<int> pq;
        vector< vector<int> > ans;
        int maxValue=0;
        pq.insert(0);
        for(int i=0;i<A.size();i++){
            if(A[i][2]==0){
                pq.insert(A[i][1]);
            }
            else{
                pq.erase(pq.find(A[i][1]));
            }
            auto itr=pq.end();
            itr--;
            if(maxValue!=*itr)
            ans.push_back({A[i][0],*itr});
            maxValue=*itr;
        }
        return ans;
    }
};