Q53 The Skyline Problem - LeetCode
Tue Jan 31 2023 08:31:24 GMT+0000 (UTC)
Saved by @Ayush_dabas07
class Solution { //make a pair class to store x coordinate and height, write a compareTo function // to compare based increasing order of x coordinate , if x are same , compare //based on increasing height public class pair implements Comparable<pair>{ int x ; int ht ; pair(int x , int ht){ this.x = x ; this.ht = ht; } //compare to function public int compareTo(pair o){ if(this.x != o.x) return this.x - o.x; //increasing order else return this.ht - o.ht; //increasing order } } public List<List<Integer>> getSkyline(int[][] buildings) { // input building x and height List<pair> input = new ArrayList<>(); for(int i =0 ; i< buildings.length ; i++){ int sp = buildings[i][0]; //starting point int ep = buildings[i][1]; //ending point int ht = buildings[i][2]; //height //adding (sp,ht) and (ep,ht) seperately and adding -ht in sp to distinguish //that it is a starting point and to handle edge cases (see register) pair s = new pair(sp,-ht); pair e = new pair(ep,ht); input.add(s); input.add(e); } //sort the list in ascending order Collections.sort(input); //make a max priority queue PriorityQueue<Integer> maxheap = new PriorityQueue<>(Collections.reverseOrder()); List<List<Integer>> ans = new ArrayList<>(); int curr = 0; //a pointer for storing current height; maxheap.add(0); //iterate the list for(int i =0 ; i < input.size() ;i++){ int x = input.get(i).x; int ht = input.get(i).ht; //if starting point if(ht < 0) maxheap.add(-ht); //adding -(-ht) in pq to make it positive else maxheap.remove(ht); //o(n) function in PQ //if curr height and active building's max height are same ,continue if(curr != maxheap.peek()){ List<Integer> temp = new ArrayList<>(); temp.add(x); temp.add(maxheap.peek()); ans.add(temp); //updating current height to active building's height curr = maxheap.peek(); } } return ans; } }
Comments