The Skyline Problem

                                            
class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        vector<vector<int>> result;
        
        multiset<pair<int, int>> criticalPoints;
        for (auto& b : buildings) {
            criticalPoints.emplace(b[0], -b[2]);
            criticalPoints.emplace(b[1], b[2]);
        }
        
        multiset<int> heights = {0};
        vector<int> prev = {0, 0};
        for (auto& cp : criticalPoints) {
            int x = cp.first;
            int h = abs(cp.second);
            
            if (cp.second < 0) {
                heights.insert(h);
            } else {
                heights.erase(heights.find(h));
            }
            
            int maxHeight = *heights.rbegin();
            if (prev[1] != maxHeight) {
                result.push_back({x, maxHeight});
                prev[0] = x;
                prev[1] = maxHeight;
            }
        }
        
        return result;
    }
};

                                            
class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        List<List<Integer>> result = new ArrayList<>();
        List<int[]> buildingPoints = new ArrayList<>();
        
        for (int[] building : buildings) {
            buildingPoints.add(new int[]{building[0], -building[2]});
            buildingPoints.add(new int[]{building[1], building[2]});
        }
        
        Collections.sort(buildingPoints, (a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            } else {
                return a[1] - b[1];
            }
        });
        
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
        maxHeap.offer(0);
        int prevMaxHeight = 0;
        
        for (int[] buildingPoint : buildingPoints) {
            if (buildingPoint[1] < 0) {
                maxHeap.offer(-buildingPoint[1]);
            } else {
                maxHeap.remove(buildingPoint[1]);
            }
            
            int currentMaxHeight = maxHeap.peek();
            
            if (prevMaxHeight != currentMaxHeight) {
                result.add(Arrays.asList(buildingPoint[0], currentMaxHeight));
                prevMaxHeight = currentMaxHeight;
            }
        }
        
        return result;
    }
}

                                            
class Solution(object):
    def getSkyline(self, buildings):
        """
        :type buildings: List[List[int]]
        
        """
        import heapq
        res = []
        points = []
        for building in buildings:
            points.append((building[0], -building[2]))
            points.append((building[1], building[2]))
        
        points.sort()
        pq = [0]
        prev_max = 0
        
        for point in points:
            if point[1] < 0:
                heapq.heappush(pq, point[1])
            else:
                pq.remove(-point[1])
                heapq.heapify(pq)
            
            curr_max = -pq[0]
            if curr_max != prev_max:
                res.append([point[0], curr_max])
                prev_max = curr_max
        
        return res

To solve this coding challenge, we need to determine the skyline formed by a collection of rectangular buildings. Each building is defined by three parameters: the x-coordinate of its left edge, the x-coordinate of its right edge, and its height. The skyline is visualized as the outer contour when viewed from a distance.

Explanation

Here's how we can approach the problem step-by-step:

Understanding the Problem: The skyline is a series of key points where the height of the skyline changes. A key point
[x, y]

represents a point on the skyline at coordinate
x

with height
y

. The goal is to return these key points in sorted order by
x

.
Event Points Concept: We can think of each building contributing two events:

A start event when the building begins.
An end event when the building ends.

We'll process these events in sorted order of their x-coordinate values.

Heap Data Structure: To efficiently manage the heights of the buildings we are currently "inside," we can use a max-heap. As we traverse through the event points:

On encountering a start event, we add the building's height to the heap.
On encountering an end event, we remove the building's height from the heap.

Detecting Key Points: As we add or remove heights, the maximum height in the heap will tell us the current height of the skyline at that x-coordinate. If there's a change in this height from the previous maximum height, it represents a key point.
Edge Cases: Handle scenarios where there are overlapping buildings, and buildings that end/begin at the same x-coordinate.

Detailed Steps in Pseudocode

Initialize Structures:

Use a list to store the events.
Use a max-heap to keep track of active heights.
Track the previous height to detect changes in the skyline.

Create Events: For each building, create two events - one for the start and one for the end and store them in a sorted list.
Process Events:

For each event, update the heap and check if there's a change in the maximum height in the heap.

Store Key Points: Whenever there's a change in the maximum height, add this point to the result list.

Pseudocode

                                            
# Input: List of buildings
# Output: List of key points in the skyline

function getSkyline(buildings):
    # Events will store tuples in the form (x-coordinate, event type, height)
    events = []

    # Populate the events list with start and end events for all buildings
    for building in buildings:
        left_x = building[0]
        right_x = building[1]
        height = building[2]
        
        # Start event: Use negative height to differentiate from end event
        events.append((left_x, -height))
        # End event: Use positive height
        events.append((right_x, height))

    # Sort events: By x-coordinate, then by height (start events before end events)
    events.sort()

    # Result list for storing key points of the skyline
    result = []
    
    # Max-heap to keep track of the tallest building at current x-coordinate
    current_heights = [0]
    import heapq

    # Initialize previous maximum height to 0
    previous_max_height = 0

    for event in events:
        x = event[0]
        height = event[1]

        if height < 0: # Start event
            # Add building height to max-heap (negative because heapq is a min-heap)
            heapq.heappush(current_heights, height)
        else: # End event
            # Remove building height from max-heap
            current_heights.remove(-height)
            heapq.heapify(current_heights)

        # Get the current maximum height from the heap (current tallest building)
        current_max_height = -current_heights[0]

        # If there's a change in the maximum height, it means we have a key point
        if current_max_height != previous_max_height:
            result.append([x, current_max_height])
            previous_max_height = current_max_height

    return result

Summary

We've explained how to use event points to represent the start and end of buildings.
Use a heap to keep track of the maximum height at any given x-coordinate.
Process events in sorted order to construct the skyline incrementally by detecting height changes.
Ensure proper handling of corner cases where buildings overlap or have shared edges.

By following these steps, we can efficiently compute the desired skyline for a given set of buildings.