# Leetcode The Skyline problem solution

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.

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