Leetcode The Skyline problem solution YASH PAL, 31 July 2024 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. Topics we are covering Toggle Problem solution in Python.Problem solution in Java.Problem solution in C++. 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; } }; coding problems solutions