Example: SkyLine - rFronteddu/general_wiki GitHub Wiki

class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        List<List<Integer>> skyline = new ArrayList<>();
        List<int[]> keyPoints = new ArrayList<>();
        
        // Create key points from building edges
        for (int[] building : buildings) {
            // For left edge, use negative height; for right edge, use positive height
            // we want to be sure when we sort left edges come before right edges
            keyPoints.add (new int[]{building[0], -building[2]}); 
            keyPoints.add (new int[]{building[1], building[2]});
        }
        
    
        keyPoints.sort((a, b) -> {
            // Sort key points by x-coordinate and then by height
            if (a[0] != b[0]) {
                return a[0] - b[0];
            } 
            return a[1] - b[1];
        });
        
        // Max heap to store heights of active buildings
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        // Add a dummy height for when there are no buildings
        maxHeap.offer(0);

        int prevHeight = 0;
        for (int[] point : keyPoints) {
            int x = point[0];
            int height = Math.abs(point[1]);
            
            if (point[1] < 0) { 
                // Left edge
                // we use negative for left => max height of active building will be top
                maxHeap.offer(height);
            } else { 
                // Right edge
                // at a building end we should remove the height of the corresponding building
                maxHeap.remove(height);
            }
            
            int currHeight = maxHeap.peek();
            if (currHeight != prevHeight) {
                // if different we must add a new key point
                List<Integer> keyPoint = new ArrayList<>();
                keyPoint.add(x);
                keyPoint.add(currHeight);
                skyline.add(keyPoint);
                prevHeight = currHeight;
            }
        }
        return skyline;
    }   
}