AlgoInsight

Q&A

The skyline problem in C++

By AlgoInsight Team2026-06-07algorithmsdata-structuresccpp

Overview

Given buildings as triples (left, right, height), the skyline is the sequence of points (x, height) marking where the top profile of the city changes as you scan horizontally. Overlapping buildings merge; only the tallest at each x is visible. The efficient approach is a sweep line over the buildings' edges combined with a structure that quickly yields the current maximum height.

graph TD
    A[Buildings: left, right, height] --> B[Create edge events: left=+h, right=-h]
    B --> C[Sort events by x]
    C --> D[Sweep left→right, maintain max-heap of active heights]
    D --> E{Max height changed?}
    E -->|yes| F[Record key point x, newMaxHeight]
    E -->|no| D
    style D fill:#1e1b4b,color:#fff

The Sweep-Line + Heap Approach

  1. Turn each building into two events: a left edge (height begins) and a right edge (height ends).
  2. Sort events by x-coordinate (with tie-breaking rules so simultaneous edges process correctly).
  3. Sweep through events maintaining a collection of active heights (heights of buildings currently overlapping the sweep line).
  4. After each event, find the current max height; whenever it changes from the previous max, record a key point (x, newMaxHeight).

The current max comes from a max-heap or an ordered multiset - that's what makes it O(n log n).

C++ Implementation (multiset of active heights)

#include <vector>
#include <algorithm>
#include <map>
using namespace std;

vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
    // events: (x, height). Left edge: negative height (so it sorts before right
    // at same x and marks "start"); right edge: positive height ("end").
    vector<pair<int,int>> events;
    for (auto& b : buildings) {
        events.push_back({b[0], -b[2]});   // left edge (start)
        events.push_back({b[1],  b[2]});   // right edge (end)
    }
    sort(events.begin(), events.end());

    multiset<int> heights = {0};           // active heights, ground = 0
    int prev = 0;
    vector<vector<int>> result;

    for (auto& [x, h] : events) {
        if (h < 0) heights.insert(-h);     // start: add the height
        else       heights.erase(heights.find(h));  // end: remove one instance

        int cur = *heights.rbegin();       // current max height
        if (cur != prev) {                 // height changed → key point
            result.push_back({x, cur});
            prev = cur;
        }
    }
    return result;
}

Why the encoding tricks?

Example

Buildings: [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Skyline:   [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]

Each pair marks an x where the visible top height changes.

Complexity

A divide-and-conquer solution (split buildings, recursively compute skylines, merge - like merge sort) is also O(n log n) and is a common alternative answer.

Why This Matters in Interviews

The skyline problem (LeetCode 218, "hard") tests sweep-line technique and clever use of a priority structure. The signals: modeling buildings as edge events, sorting with correct tie-breaking, maintaining active heights in a max-heap/multiset to get the current maximum, and recording a key point only when the max changes. The subtle tie-breaking (encoding left edges as negative heights) and the ground-level sentinel are exactly the details interviewers probe. Mentioning the divide-and-conquer alternative shows breadth.

Common Pitfalls

References

More answers