The Skyline Problem

hard heap divide and conquer ordered set sweep line

Problem

Given a list of buildings as [left, right, height], return the skyline outline as a list of "key points" [x, y] in left-to-right order, where each key point is the left endpoint of a horizontal segment.

Inputbuildings = [[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]]

A corner is emitted only when the current maximum height in the heap changes.

buildings (l:r:h separated by ';')

import heapq

def get_skyline(buildings):
    events = []
    for l, r, h in buildings:
        events.append((l, -h, r))   # start
        events.append((r, 0, 0))    # end marker
    events.sort()
    res = []
    heap = [(0, float('inf'))]      # (-height, end)
    for x, negH, r in events:
        if negH != 0:
            heapq.heappush(heap, (negH, r))
        while heap[0][1] <= x:
            heapq.heappop(heap)
        cur = -heap[0][0]
        if not res or res[-1][1] != cur:
            res.append([x, cur])
    return res

function getSkyline(buildings) {
  const events = [];
  for (const [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]);
  const res = [];
  const heap = [[0, Infinity]]; // [-h, end] sorted as max-heap by -h
  const sortHeap = () => heap.sort((a, b) => a[0] - b[0]);
  for (const [x, negH, r] of events) {
    if (negH !== 0) { heap.push([negH, r]); sortHeap(); }
    while (heap[0][1] <= x) heap.shift();
    const cur = -heap[0][0];
    if (res.length === 0 || res[res.length - 1][1] !== cur) res.push([x, cur]);
  }
  return res;
}

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]});
            events.add(new int[]{b[1], 0, 0});
        }
        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) -> a[0] - b[0]);
        heap.offer(new int[]{0, Integer.MAX_VALUE});
        for (int[] e : events) {
            if (e[1] != 0) heap.offer(new int[]{e[1], e[2]});
            while (heap.peek()[1] <= e[0]) heap.poll();
            int cur = -heap.peek()[0];
            if (res.isEmpty() || res.get(res.size()-1).get(1) != cur)
                res.add(Arrays.asList(e[0], cur));
        }
        return res;
    }
}

vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
    vector<array<int, 3>> events;
    for (auto& b : buildings) {
        events.push_back({b[0], -b[2], b[1]});
        events.push_back({b[1], 0, 0});
    }
    sort(events.begin(), events.end());
    vector<vector<int>> res;
    priority_queue<pair<int, int>> heap;  // (height, end)
    heap.push({0, INT_MAX});
    for (auto& e : events) {
        if (e[1] != 0) heap.push({-e[1], e[2]});
        while (heap.top().second <= e[0]) heap.pop();
        int cur = heap.top().first;
        if (res.empty() || res.back()[1] != cur) res.push_back({e[0], cur});
    }
    return res;
}

Explanation

The outline of the skyline only changes at building edges, and at any x-position the skyline height is simply the tallest building currently covering that spot. So we do a sweep line across all edges and keep a max-heap of active heights.

We turn each building into two events: a start at its left edge (stored as -h so heap ordering works, paired with its right end) and an end marker at its right edge. We sort all events by x. A sentinel (0, ∞) sits in the heap so the ground height is always available.

As we sweep, a start event pushes (-h, end) into the heap. Before reading the current tallest, we do lazy deletion: pop any heap top whose end is at or before the current x, since those buildings no longer cover this point. The remaining top gives cur, the current max height.

Whenever cur differs from the last emitted height, we record a key point [x, cur], because that is exactly where the skyline steps up or down.

Example: with a tall building [3,7,15] overlapping a shorter [2,9,10], the skyline rises to 15 at x=3, then drops back to 10 at x=7 when the tall one ends, producing points like [3,15] and [7,12] as the heights change.

Time: O(n log n) Space: O(n)