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