The Skyline Problem asks you to compute the "skyline" formed by a collection of rectangular buildings in a city. Each building is represented by a triplet [left, right, height] where:
left: x-coordinate where the building startsright: x-coordinate where the building ends (not included)height: the building's height[x, height] coordinates, sorted by ascending x. A critical point is where the height of the skyline changes.
buildings, where each building is [left, right, height][x, height] points, sorted by x
At first glance, the problem seems to require drawing the silhouette of overlapping rectangles and identifying where the outline changes height. A brute-force approach could be to simulate the entire x-axis, tracking the tallest building at each integer point, but this is both slow and memory-intensive, especially for large coordinate ranges.
To optimize, it's key to notice that the skyline only changes at building edges (start or end). Rather than sweep through every x, we can focus only on these "events." At each event, we need to quickly know what the current tallest building is. This suggests using a data structure that efficiently gives us the maximum height at any moment.
The challenge then becomes: how do we process these events efficiently, and how do we keep track of the current set of active buildings as we move from left to right?
The optimal solution uses a sweep line algorithm with a max-heap (priority queue) to efficiently track the tallest building at any given x-coordinate. Here’s the step-by-step approach:
x = left, height negative to indicate start), and one for the end (x = right, height positive to indicate end).[x, current max height] to the result as a critical point.We use a heap because it allows us to efficiently add and remove building heights, and always get the current tallest building in O(log n) time.
Consider the input buildings = [[2,9,10], [3,7,15], [5,12,12], [15,20,10], [19,24,8]].
Step 1: Create Events
[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
Brute-force Approach:
The Skyline Problem is elegantly solved by converting building edges into events, sorting them, and processing them with a max-heap to track the current tallest building. By focusing only on points where the skyline can possibly change, and using efficient data structures, we avoid unnecessary work and achieve optimal performance. The key insight is that the skyline only changes at building boundaries, and a priority queue allows us to always know the current outline in O(log n) time.
import heapq
class Solution:
def getSkyline(self, buildings):
# Create events: (x, height, right)
events = []
for left, right, height in buildings:
events.append((left, -height, right)) # building enters
events.append((right, 0, 0)) # building leaves
# Sort events: first by x, then by height
events.sort()
# Result and heap (max-heap by negating height)
res = []
# heap: (neg_height, end)
heap = [(0, float('inf'))]
for x, negH, R in events:
# Remove buildings from heap that have ended
while heap[0][1] <= x:
heapq.heappop(heap)
if negH != 0:
heapq.heappush(heap, (negH, R))
# Current max height
curr = -heap[0][0]
# If height changed, add to result
if not res or res[-1][1] != curr:
res.append([x, curr])
return res
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
vector<pair<int, int>> events;
for (auto& b : buildings) {
// Entering event: negative height
events.emplace_back(b[0], -b[2]);
// Leaving event: height 0
events.emplace_back(b[1], b[2]);
}
sort(events.begin(), events.end());
vector<vector<int>> res;
// Max-heap: pair<height, end>
multiset<int> heights = {0};
unordered_map<int, int> to_remove;
int prev = 0;
for (int i = 0; i < events.size(); ) {
int x = events[i].first;
// Process all events at the same x
while (i < events.size() && events[i].first == x) {
int h = events[i].second;
if (h < 0) {
heights.insert(-h);
} else {
heights.erase(heights.find(h));
}
++i;
}
int curr = *heights.rbegin();
if (res.empty() || res.back()[1] != curr) {
res.push_back({x, curr});
}
}
return res;
}
};
import java.util.*;
class Solution {
public List<List<Integer>> getSkyline(int[][] buildings) {
List<int[]> events = new ArrayList<>();
for (int[] b : buildings) {
events.add(new int[]{b[0], -b[2], b[1]}); // start
events.add(new int[]{b[1], 0, 0}); // end
}
events.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
List<List<Integer>> res = new ArrayList<>();
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
heap.offer(new int[]{0, Integer.MAX_VALUE});
for (int[] e : events) {
int x = e[0], h = e[1], r = e[2];
while (heap.peek()[1] <= x) heap.poll();
if (h != 0) heap.offer(new int[]{-h, r});
int curr = heap.peek()[0];
if (res.isEmpty() || res.get(res.size()-1).get(1) != curr)
res.add(Arrays.asList(x, curr));
}
// convert heights back to positive
for (List<Integer> point : res) {
point.set(1, Math.abs(point.get(1)));
}
return res;
}
}
class MaxHeap {
constructor() {
this.heap = [0];
}
insert(val) {
this.heap.push(val);
this._bubbleUp();
}
remove(val) {
let idx = this.heap.indexOf(val);
if (idx === -1) return;
this.heap[idx] = this.heap[this.heap.length - 1];
this.heap.pop();
this._bubbleDown(idx);
}
max() {
return this.heap.length > 1 ? this.heap[1] : 0;
}
_bubbleUp() {
let idx = this.heap.length - 1;
while (idx > 1 && this.heap[idx] > this.heap[Math.floor(idx/2)]) {
[this.heap[idx], this.heap[Math.floor(idx/2)]] = [this.heap[Math.floor(idx/2)], this.heap[idx]];
idx = Math.floor(idx/2);
}
}
_bubbleDown(idx) {
while (2*idx < this.heap.length) {
let j = 2*idx;
if (j+1 < this.heap.length && this.heap[j+1] > this.heap[j]) j++;
if (this.heap[idx] >= this.heap[j]) break;
[this.heap[idx], this.heap[j]] = [this.heap[j], this.heap[idx]];
idx = j;
}
}
}
var getSkyline = function(buildings) {
let events = [];
for (let [l, r, h] of buildings) {
events.push([l, -h, r]);
events.push([r, 0, 0]);
}
events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
let res = [];
let heap = new MaxHeap();
heap.insert(0);
for (let [x, negH, R] of events) {
while (heap.heap.length > 1 && heap.heap[1] !== 0 && heap.heap[1] <= x) {
heap.remove(heap.heap[1]);
}
if (negH !== 0) heap.insert(-negH);
let curr = heap.max();
if (!res.length || res[res.length-1][1] !== curr) res.push([x, curr]);
}
return res;
};