Skyline Problem

Problem

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.

The geometric information of each building is given in the array buildings where buildings[i] = [lefti, righti, heighti]:

• lefti is the x coordinate of the left edge of the ith building.
• righti is the x coordinate of the right edge of the ith building.
• heighti is the height of the ith building.

You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

The skyline should be represented as a list of “key points” sorted by their x-coordinate in the form [[x1,y1],[x2,y2],...]. Each key point is the left endpoint of some horizontal segment in the skyline except the last point in the list, which always has a y-coordinate 0 and is used to mark the skyline’s termination where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline’s contour.

Note: There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...,[2 3],[4 5],[7 5],[11 5],[12 7],...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...,[2 3],[4 5],[12 7],...]

Example 1:

Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
Explanation:
Figure A shows the buildings of the input.
Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.

Example 2:

Input: buildings = [[0,2,3],[2,5,3]]
Output: [[0,3],[5,0]]

Solution

Method 1 - Using Sorting and maxheap

How do we solve it? If we observe closely, buildings form a series of intervals that overlap to varying degrees. Essentially, we need to determine strips such that, at each strip’s left edge, the height of the strip equals the tallest height of all overlapping buildings. This means identifying overlapping intervals, with each building representing an interval and its height as the interval’s “weight.”

The problem is similar to : Maximum intervals overlap (Count max alive elephants in a period) and Maximum CPU Load For Running Tasks. Left and right coordinates are like interval and height is value in the interval. We have to pick the max value in the interval.

This problem can be viewed as managing 2*n edges, where each edge has an x-coordinate and a height value. We use a max heap to process each of these edges effectively.

1. Event Creation: Create an event for each building’s start and end points. Each building is represented by two events: one for the start (with positive height) and one for the end (with negative height).
2. Event Sorting: Sort events based on the x-coordinate. When two events have the same x-coordinate, the start event should come before the end event.
3. Processing Events: Use a max-heap to keep track of the current heights of buildings. As we process each event:
   • If it’s a start event, add the building’s height to the heap.
   • If it’s an end event, remove the building’s height from the heap.
4. Recording Key Points: After processing each event, the maximum height in the heap represents the current height of the skyline at that x-coordinate. If the height changes, record the x-coordinate and the new height as a key point.

How do we solve it? If we notice closely then we will see that the buildings form a range of intervals where some of them are overlapping with each other. We need to basically find strips such that if an interval overlaps at the left point of the strip then height of the strip would be the maximum height of all the overlapping ranges. So, the idea is to find overlapping intervals if we consider each building as an interval and the height of the building as the weight of the interval.

Code

Java

class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        List<int[]> events = new ArrayList<>();
        for (int[] building : buildings) {
            events.add(new int[] {building[0], -building[2]}); // Start event
            events.add(new int[] {building[1], building[2]});  // End event
        }
        events.sort((a, b) -> (a[0] != b[0]) ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.add(0);
        List<List<Integer>> ans = new ArrayList<>();
        int prevMaxHeight = 0;

        for (int[] event : events) {
            int x = event[0], h = event[1];
            if (h < 0) {  // start event
                maxHeap.add(-h);
            } else {  // end event
                maxHeap.remove(h);
            }
            int currMaxHeight = maxHeap.peek();
            if (currMaxHeight != prevMaxHeight) {
                ans.add(Arrays.asList(x, currMaxHeight));
                prevMaxHeight = currMaxHeight;
            }
        }

        return ans;
    }
}

Python

class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        events = []
        for (l, r, h) in buildings:
            events.append((l, -h))  # Start event
            events.append((r, h))   # End event
        events.sort(key=lambda x: (x[0], x[1]))

        max_heap = [0]
        heapq.heapify(max_heap)
        ans = []
        prevMaxHeight = 0

        for x, h in events:
            if h < 0:  # start event
                heapq.heappush(max_heap, h)
            else:  # end event
                max_heap.remove(-h)
                heapq.heapify(max_heap)
            
            currMaxHeight = -max_heap[0]
            if currMaxHeight != prevMaxHeight:
                ans.append([x, currMaxHeight])
                prevMaxHeight = currMaxHeight

        return ans

Complexity

• ⏰ Time complexity: O(n log n), where n is the number of buildings, due to sorting the events and the operations on the max-heap.
• 🧺 Space complexity: O(n), for storing the events and the heap.