#86 · Heap / Priority Queue

The Skyline Problem

Given buildings as [left, right, height] triples sorted by left edge, return the skyline: the list of key points [x, height] where the outline of the merged silhouette changes height, ending with a point on the ground.

HardLeetCode

Being examined
New / inserted
Kept / merged / answer
Removed / conflict
Untouched

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Sweep line over edge coordinates

The outline can only change where a building starts or ends. A vertical line sweeps left to right over those coordinates; at each one, the outline height is the tallest building that covers it.

Memory layout

A sorted array of distinct x coordinates, or of start / end events.

Operation	Cost
sorting the edges	O(n log n)

Max-heap with lazy deletion

Holds (height, right edge) for buildings entered so far. The top is the tallest one. Instead of removing a building when it ends (which a heap cannot do efficiently), expired entries are popped only when they reach the top.

Memory layout

A contiguous array where children of i are at 2i + 1 and 2i + 2; at most n entries.

Operation	Cost
push / pop	O(log n)
peek	O(1)

Skyline lists and merging

A skyline is a sorted list of (x, height) key points. Two skylines merge with two pointers in linear time by tracking each side's current height and emitting max(h1, h2) whenever it changes.

Memory layout

Plain lists of pairs; merging is sequential and cache friendly.

Operation	Cost
merge	O(a + b)

Why it fits

The answer is a function of the maximum height at each x, which is exactly what a max-heap tracks while buildings enter and leave.
Lazy deletion works because only the top matters: a stale entry buried under taller entries cannot affect the outline.
Divide and conquer fits because a skyline is closed under merging: the outline of two groups is a simple pointwise maximum of their outlines.

Why alternatives degrade

Painting a height array over x:: O(total width) memory and time, and coordinates can reach 2³¹ − 1.
Sorted list of heights without a heap:: Removal and max are O(n) per event, giving O(n²).
Segment tree over compressed coordinates:: Works (range chmax, point query) but is heavier than a heap for the same O(n log n).

Four approaches, from naive to production

1 · beginner

Height at every edge by scanning all buildings

time O(n²)space O(n)

Collect all distinct edge coordinates. At each one, scan every building to find the tallest that covers it; whenever this height differs from the previous one, record a key point.

vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
    set<int> edges;
    for (auto& b : buildings) { edges.insert(b[0]); edges.insert(b[1]); }
    vector<int> xs(edges.begin(), edges.end());
    vector<vector<int>> result;
    int prev = 0;
    for (int x : xs) {
        int height = 0;
        for (auto& b : buildings) {
            if (b[0] <= x && x < b[1]) height = max(height, b[2]);
        }
        if (height != prev) { result.push_back({x, height}); prev = height; }
    }
    return result;
}

public List<List<Integer>> getSkyline(int[][] buildings) {
    TreeSet<Integer> edges = new TreeSet<>();
    for (int[] b : buildings) { edges.add(b[0]); edges.add(b[1]); }
    List<Integer> xs = new ArrayList<>(edges);
    List<List<Integer>> result = new ArrayList<>();
    int prev = 0;
    for (int x : xs) {
        int height = 0;
        for (int[] b : buildings) {
            if (b[0] <= x && x < b[1]) height = Math.max(height, b[2]);
        }
        if (height != prev) { result.add(Arrays.asList(x, height)); prev = height; }
    }
    return result;
}

def get_skyline(buildings):
    xs = sorted({v for l, r, h in buildings for v in (l, r)})
    result = []
    prev = 0
    for x in xs:
        height = 0
        for l, r, h in buildings:
            if l <= x < r: height = max(height, h)
        if height != prev:
            result.append([x, height]); prev = height
    return result

function getSkyline(buildings: number[][]): number[][] {
  const xs = [...new Set(buildings.flatMap(([l, r]) => [l, r]))].sort((a, b) => a - b);
  const result: number[][] = [];
  let prev = 0;
  for (const x of xs) {
    let height = 0;
    for (const [l, r, h] of buildings) {
      if (l <= x && x < r) height = Math.max(height, h);
    }
    if (height !== prev) { result.push([x, height]); prev = height; }
  }
  return result;
}

Flaws & bottlenecks

For each of up to 2n coordinates it scans all n buildings.
The same buildings are re-tested at neighbouring coordinates.
Too slow for n = 10⁴.

Interviewer cross-questions

Why only edge coordinates?

Say: Between two consecutive edges the set of covering buildings does not change, so the height is constant there.

Why x < r and not x <= r?

Say: A building covers [l, r); at its right edge it has already ended, which is why the outline can drop exactly at r.

What avoids rescanning?

Say: Keep the covering buildings in a data structure with fast maximum, such as a max-heap, as the sweep advances.

2 · intermediate

Sorted start / end events with an active list

time O(n²)space O(n)

Turn each building into a start event (l, −h) and an end event (r, +h), sort them, and maintain a list of active heights. After each event compare the current maximum with the previous one.

vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
    vector<pair<int, int>> events;
    for (auto& b : buildings) {
        events.push_back({b[0], -b[2]});
        events.push_back({b[1], b[2]});
    }
    sort(events.begin(), events.end());
    vector<int> active;
    vector<vector<int>> result;
    int prev = 0;
    for (auto& [x, h] : events) {
        if (h < 0) active.push_back(-h);
        else active.erase(find(active.begin(), active.end(), h));
        int cur = active.empty() ? 0 : *max_element(active.begin(), active.end());
        if (cur != prev) { result.push_back({x, cur}); prev = cur; }
    }
    return result;
}

public List<List<Integer>> getSkyline(int[][] buildings) {
    List<int[]> events = new ArrayList<>();
    for (int[] b : buildings) {
        events.add(new int[]{b[0], -b[2]});
        events.add(new int[]{b[1], b[2]});
    }
    events.sort((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
    List<Integer> active = new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();
    int prev = 0;
    for (int[] e : events) {
        int x = e[0], h = e[1];
        if (h < 0) active.add(-h);
        else active.remove(Integer.valueOf(h));
        int cur = active.isEmpty() ? 0 : Collections.max(active);
        if (cur != prev) { result.add(Arrays.asList(x, cur)); prev = cur; }
    }
    return result;
}

def get_skyline(buildings):
    events = []
    for l, r, h in buildings:
        events.append((l, -h))
        events.append((r, h))
    events.sort()
    active = []
    result = []
    prev = 0
    for x, h in events:
        if h < 0: active.append(-h)
        else: active.remove(h)
        cur = max(active) if active else 0
        if cur != prev:
            result.append([x, cur]); prev = cur
    return result

function getSkyline(buildings: number[][]): number[][] {
  const events: number[][] = [];
  for (const [l, r, h] of buildings) {
    events.push([l, -h]);
    events.push([r, h]);
  }
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
  const active: number[] = [];
  const result: number[][] = [];
  let prev = 0;
  for (const [x, h] of events) {
    if (h < 0) active.push(-h);
    else active.splice(active.indexOf(h), 1);
    const cur = active.length === 0 ? 0 : Math.max(...active);
    if (cur !== prev) { result.push([x, cur]); prev = cur; }
  }
  return result;
}

Flaws & bottlenecks

Removing from and scanning the active list costs O(n) per event.
The tie-breaking order of events (taller starts first, shorter ends first) is subtle.
Math.max over a spread array can overflow the argument limit for huge lists.

Interviewer cross-questions

Why store starts as −h?

Say: Sorting by (x, value) then puts starts before ends at the same x, and among starts the tallest first; among ends the shortest first. That avoids spurious key points at equal x.

What if two buildings touch (one ends where another starts)?

Say: Starts are processed before ends at the same x, so the new building is active before the old one is removed and no dip to ground is emitted.

How do you speed up the maximum?

Say: Use a max-heap (with lazy deletion) or a balanced multiset so max and remove cost O(log n).

3 · advanced

Sweep line with a max-heap and lazy deletion

time O(n log n)space O(n)

Sweep over the distinct x coordinates. Push every building that has started into a max-heap keyed by height (storing its right edge). Pop the top while it has already ended. The top's height is the outline height.

vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
    set<int> edges;
    for (auto& b : buildings) { edges.insert(b[0]); edges.insert(b[1]); }
    vector<int> xs(edges.begin(), edges.end());
    priority_queue<pair<int, int>> heap; // (height, right edge)
    vector<vector<int>> result;
    size_t i = 0; int prev = 0;
    for (int x : xs) {
        while (i < buildings.size() && buildings[i][0] <= x) {
            heap.push({buildings[i][2], buildings[i][1]});
            i++;
        }
        while (!heap.empty() && heap.top().second <= x) heap.pop();
        int height = heap.empty() ? 0 : heap.top().first;
        if (height != prev) { result.push_back({x, height}); prev = height; }
    }
    return result;
}

public List<List<Integer>> getSkyline(int[][] buildings) {
    TreeSet<Integer> edges = new TreeSet<>();
    for (int[] b : buildings) { edges.add(b[0]); edges.add(b[1]); }
    List<Integer> xs = new ArrayList<>(edges);
    PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[0] - a[0]); // {height, right edge}
    List<List<Integer>> result = new ArrayList<>();
    int i = 0, prev = 0;
    for (int x : xs) {
        while (i < buildings.length && buildings[i][0] <= x) {
            heap.add(new int[]{buildings[i][2], buildings[i][1]});
            i++;
        }
        while (!heap.isEmpty() && heap.peek()[1] <= x) heap.poll();
        int height = heap.isEmpty() ? 0 : heap.peek()[0];
        if (height != prev) { result.add(Arrays.asList(x, height)); prev = height; }
    }
    return result;
}

def get_skyline(buildings):
    xs = sorted({v for l, r, h in buildings for v in (l, r)})
    heap = []  # (-height, right edge)
    result = []
    i = prev = 0
    for x in xs:
        while i < len(buildings) and buildings[i][0] <= x:
            heapq.heappush(heap, (-buildings[i][2], buildings[i][1]))
            i += 1
        while heap and heap[0][1] <= x: heapq.heappop(heap)
        height = -heap[0][0] if heap else 0
        if height != prev:
            result.append([x, height]); prev = height
    return result

function getSkyline(buildings: number[][]): number[][] {
  const xs = [...new Set(buildings.flatMap(([l, r]) => [l, r]))].sort((a, b) => a - b);
  const heap = new Heap<number[]>((a, b) => a[0] > b[0]);
  const result: number[][] = [];
  let i = 0, prev = 0;
  for (const x of xs) {
    while (i < buildings.length && buildings[i][0] <= x) {
      heap.push([buildings[i][2], buildings[i][1]]);
      i++;
    }
    while (heap.size > 0 && heap.peek()[1] <= x) heap.pop();
    const height = heap.size === 0 ? 0 : heap.peek()[0];
    if (height !== prev) { result.push([x, height]); prev = height; }
  }
  return result;
}

class Heap<T> {
  private a: T[] = [];
  constructor(private before: (x: T, y: T) => boolean) {}
  get size() { return this.a.length; }
  peek(): T { return this.a[0]; }
  push(v: T) {
    const a = this.a;
    a.push(v);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (!this.before(a[i], a[p])) break;
      [a[i], a[p]] = [a[p], a[i]];
      i = p;
    }
  }
  pop(): T {
    const a = this.a;
    const top = a[0];
    const last = a.pop()!;
    if (a.length) {
      a[0] = last;
      let i = 0;
      for (;;) {
        let m = i;
        const l = 2 * i + 1, r = l + 1;
        if (l < a.length && this.before(a[l], a[m])) m = l;
        if (r < a.length && this.before(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]];
        i = m;
      }
    }
    return top;
  }
}

Flaws & bottlenecks

Stale entries can sit inside the heap until they reach the top.
Needs the buildings sorted by left edge (given by the problem; otherwise sort first).
Coordinates are compared with <=, which is a classic off-by-one trap.

Interviewer cross-questions

Why is lazy deletion correct?

Say: Only the maximum matters. An expired entry below the top cannot change the outline, and an expired entry at the top is removed before reading it.

Why is each building pushed and popped at most once?

Say: The pointer i only moves forward and every pop removes an entry for good: total O(n log n).

What changes for 10⁵ buildings with huge coordinates?

Say: Nothing: the algorithm depends on the number of edges, not on coordinate values, so no coordinate compression is needed.

4 · expert

Divide and conquer: merge two skylines

time O(n log n)space O(n)

The skyline of one building is [(l, h), (r, 0)]. Recursively compute the skylines of the two halves and merge them like a merge sort, tracking each side's current height and emitting max(h1, h2) when it changes.

vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
    function<vector<vector<int>>(const vector<vector<int>>&, const vector<vector<int>>&)> merge =
        [](const vector<vector<int>>& a, const vector<vector<int>>& b) {
            vector<vector<int>> out;
            size_t i = 0, j = 0; int h1 = 0, h2 = 0;
            while (i < a.size() || j < b.size()) {
                long long xa = i < a.size() ? a[i][0] : LLONG_MAX;
                long long xb = j < b.size() ? b[j][0] : LLONG_MAX;
                long long x = min(xa, xb);
                if (xa == x) h1 = a[i++][1];
                if (xb == x) h2 = b[j++][1];
                int h = max(h1, h2);
                if (out.empty() || out.back()[1] != h) out.push_back({(int)x, h});
            }
            return out;
        };
    function<vector<vector<int>>(int, int)> solve = [&](int lo, int hi) -> vector<vector<int>> {
        if (lo == hi) return {{buildings[lo][0], buildings[lo][2]}, {buildings[lo][1], 0}};
        int mid = (lo + hi) >> 1;
        return merge(solve(lo, mid), solve(mid + 1, hi));
    };
    return buildings.empty() ? vector<vector<int>>{} : solve(0, (int)buildings.size() - 1);
}

public List<List<Integer>> getSkyline(int[][] buildings) {
    return buildings.length == 0 ? new ArrayList<>() : solve(buildings, 0, buildings.length - 1);
}
private List<List<Integer>> merge(List<List<Integer>> a, List<List<Integer>> b) {
    List<List<Integer>> out = new ArrayList<>();
    int i = 0, j = 0, h1 = 0, h2 = 0;
    while (i < a.size() || j < b.size()) {
        long xa = i < a.size() ? a.get(i).get(0) : Long.MAX_VALUE;
        long xb = j < b.size() ? b.get(j).get(0) : Long.MAX_VALUE;
        long x = Math.min(xa, xb);
        if (xa == x) h1 = a.get(i++).get(1);
        if (xb == x) h2 = b.get(j++).get(1);
        int h = Math.max(h1, h2);
        if (out.isEmpty() || out.get(out.size() - 1).get(1) != h) out.add(Arrays.asList((int) x, h));
    }
    return out;
}
private List<List<Integer>> solve(int[][] buildings, int lo, int hi) {
    if (lo == hi) return Arrays.asList(Arrays.asList(buildings[lo][0], buildings[lo][2]), Arrays.asList(buildings[lo][1], 0));
    int mid = (lo + hi) >> 1;
    return merge(solve(buildings, lo, mid), solve(buildings, mid + 1, hi));
}

def get_skyline(buildings):
    def merge(a, b):
        out = []
        i = j = h1 = h2 = 0
        while i < len(a) or j < len(b):
            xa = a[i][0] if i < len(a) else float('inf')
            xb = b[j][0] if j < len(b) else float('inf')
            x = min(xa, xb)
            if xa == x: h1 = a[i][1]; i += 1
            if xb == x: h2 = b[j][1]; j += 1
            h = max(h1, h2)
            if not out or out[-1][1] != h: out.append([x, h])
        return out
    def solve(lo, hi):
        if lo == hi: return [[buildings[lo][0], buildings[lo][2]], [buildings[lo][1], 0]]
        mid = (lo + hi) >> 1
        return merge(solve(lo, mid), solve(mid + 1, hi))
    return [] if not buildings else solve(0, len(buildings) - 1)

function getSkyline(buildings: number[][]): number[][] {
  const merge = (a: number[][], b: number[][]): number[][] => {
    const out: number[][] = [];
    let i = 0, j = 0, h1 = 0, h2 = 0;
    while (i < a.length || j < b.length) {
      const xa = i < a.length ? a[i][0] : Infinity;
      const xb = j < b.length ? b[j][0] : Infinity;
      const x = Math.min(xa, xb);
      if (xa === x) h1 = a[i++][1];
      if (xb === x) h2 = b[j++][1];
      const h = Math.max(h1, h2);
      if (out.length === 0 || out[out.length - 1][1] !== h) out.push([x, h]);
    }
    return out;
  };
  const solve = (lo: number, hi: number): number[][] => {
    if (lo === hi) return [[buildings[lo][0], buildings[lo][2]], [buildings[lo][1], 0]];
    const mid = (lo + hi) >> 1;
    return merge(solve(lo, mid), solve(mid + 1, hi));
  };
  return buildings.length === 0 ? [] : solve(0, buildings.length - 1);
}

Flaws & bottlenecks

Allocates new lists at every merge level.
Recursion depth is only O(log n), but the intermediate lists use O(n log n) allocations in total.
The merge must handle equal x from both sides in one step to avoid duplicate key points.

Interviewer cross-questions

Why does the merge work?

Say: The merged outline is the pointwise maximum of the two outlines, and both are step functions that change only at their own key points, so one two-pointer sweep sees every change.

What is the recurrence?

Say: T(n) = 2T(n/2) + O(n), which is O(n log n), the same as the heap solution.

When would you prefer this over the heap?

Say: When the data is distributed (merge partial skylines from workers) or you need an allocation-light, heap-free solution; it also parallelises naturally.

Synchronized code walkthrough

Showing: Height at every edge by scanning all buildings — shares the player above; click any step to jump.

vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
    set<int> edges;
    for (auto& b : buildings) { edges.insert(b[0]); edges.insert(b[1]); }
    vector<int> xs(edges.begin(), edges.end());
    vector<vector<int>> result;
    int prev = 0;
    for (int x : xs) {
        int height = 0;
        for (auto& b : buildings) {
            if (b[0] <= x && x < b[1]) height = max(height, b[2]);
        }
        if (height != prev) { result.push_back({x, height}); prev = height; }
    }
    return result;
}

public List<List<Integer>> getSkyline(int[][] buildings) {
    TreeSet<Integer> edges = new TreeSet<>();
    for (int[] b : buildings) { edges.add(b[0]); edges.add(b[1]); }
    List<Integer> xs = new ArrayList<>(edges);
    List<List<Integer>> result = new ArrayList<>();
    int prev = 0;
    for (int x : xs) {
        int height = 0;
        for (int[] b : buildings) {
            if (b[0] <= x && x < b[1]) height = Math.max(height, b[2]);
        }
        if (height != prev) { result.add(Arrays.asList(x, height)); prev = height; }
    }
    return result;
}

def get_skyline(buildings):
    xs = sorted({v for l, r, h in buildings for v in (l, r)})
    result = []
    prev = 0
    for x in xs:
        height = 0
        for l, r, h in buildings:
            if l <= x < r: height = max(height, h)
        if height != prev:
            result.append([x, height]); prev = height
    return result

function getSkyline(buildings: number[][]): number[][] {
  const xs = [...new Set(buildings.flatMap(([l, r]) => [l, r]))].sort((a, b) => a - b);
  const result: number[][] = [];
  let prev = 0;
  for (const x of xs) {
    let height = 0;
    for (const [l, r, h] of buildings) {
      if (l <= x && x < r) height = Math.max(height, h);
    }
    if (height !== prev) { result.push([x, height]); prev = height; }
  }
  return result;
}

vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
    vector<pair<int, int>> events;
    for (auto& b : buildings) {
        events.push_back({b[0], -b[2]});
        events.push_back({b[1], b[2]});
    }
    sort(events.begin(), events.end());
    vector<int> active;
    vector<vector<int>> result;
    int prev = 0;
    for (auto& [x, h] : events) {
        if (h < 0) active.push_back(-h);
        else active.erase(find(active.begin(), active.end(), h));
        int cur = active.empty() ? 0 : *max_element(active.begin(), active.end());
        if (cur != prev) { result.push_back({x, cur}); prev = cur; }
    }
    return result;
}

public List<List<Integer>> getSkyline(int[][] buildings) {
    List<int[]> events = new ArrayList<>();
    for (int[] b : buildings) {
        events.add(new int[]{b[0], -b[2]});
        events.add(new int[]{b[1], b[2]});
    }
    events.sort((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
    List<Integer> active = new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();
    int prev = 0;
    for (int[] e : events) {
        int x = e[0], h = e[1];
        if (h < 0) active.add(-h);
        else active.remove(Integer.valueOf(h));
        int cur = active.isEmpty() ? 0 : Collections.max(active);
        if (cur != prev) { result.add(Arrays.asList(x, cur)); prev = cur; }
    }
    return result;
}

def get_skyline(buildings):
    events = []
    for l, r, h in buildings:
        events.append((l, -h))
        events.append((r, h))
    events.sort()
    active = []
    result = []
    prev = 0
    for x, h in events:
        if h < 0: active.append(-h)
        else: active.remove(h)
        cur = max(active) if active else 0
        if cur != prev:
            result.append([x, cur]); prev = cur
    return result

function getSkyline(buildings: number[][]): number[][] {
  const events: number[][] = [];
  for (const [l, r, h] of buildings) {
    events.push([l, -h]);
    events.push([r, h]);
  }
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
  const active: number[] = [];
  const result: number[][] = [];
  let prev = 0;
  for (const [x, h] of events) {
    if (h < 0) active.push(-h);
    else active.splice(active.indexOf(h), 1);
    const cur = active.length === 0 ? 0 : Math.max(...active);
    if (cur !== prev) { result.push([x, cur]); prev = cur; }
  }
  return result;
}

vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
    set<int> edges;
    for (auto& b : buildings) { edges.insert(b[0]); edges.insert(b[1]); }
    vector<int> xs(edges.begin(), edges.end());
    priority_queue<pair<int, int>> heap; // (height, right edge)
    vector<vector<int>> result;
    size_t i = 0; int prev = 0;
    for (int x : xs) {
        while (i < buildings.size() && buildings[i][0] <= x) {
            heap.push({buildings[i][2], buildings[i][1]});
            i++;
        }
        while (!heap.empty() && heap.top().second <= x) heap.pop();
        int height = heap.empty() ? 0 : heap.top().first;
        if (height != prev) { result.push_back({x, height}); prev = height; }
    }
    return result;
}

public List<List<Integer>> getSkyline(int[][] buildings) {
    TreeSet<Integer> edges = new TreeSet<>();
    for (int[] b : buildings) { edges.add(b[0]); edges.add(b[1]); }
    List<Integer> xs = new ArrayList<>(edges);
    PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[0] - a[0]); // {height, right edge}
    List<List<Integer>> result = new ArrayList<>();
    int i = 0, prev = 0;
    for (int x : xs) {
        while (i < buildings.length && buildings[i][0] <= x) {
            heap.add(new int[]{buildings[i][2], buildings[i][1]});
            i++;
        }
        while (!heap.isEmpty() && heap.peek()[1] <= x) heap.poll();
        int height = heap.isEmpty() ? 0 : heap.peek()[0];
        if (height != prev) { result.add(Arrays.asList(x, height)); prev = height; }
    }
    return result;
}

def get_skyline(buildings):
    xs = sorted({v for l, r, h in buildings for v in (l, r)})
    heap = []  # (-height, right edge)
    result = []
    i = prev = 0
    for x in xs:
        while i < len(buildings) and buildings[i][0] <= x:
            heapq.heappush(heap, (-buildings[i][2], buildings[i][1]))
            i += 1
        while heap and heap[0][1] <= x: heapq.heappop(heap)
        height = -heap[0][0] if heap else 0
        if height != prev:
            result.append([x, height]); prev = height
    return result

function getSkyline(buildings: number[][]): number[][] {
  const xs = [...new Set(buildings.flatMap(([l, r]) => [l, r]))].sort((a, b) => a - b);
  const heap = new Heap<number[]>((a, b) => a[0] > b[0]);
  const result: number[][] = [];
  let i = 0, prev = 0;
  for (const x of xs) {
    while (i < buildings.length && buildings[i][0] <= x) {
      heap.push([buildings[i][2], buildings[i][1]]);
      i++;
    }
    while (heap.size > 0 && heap.peek()[1] <= x) heap.pop();
    const height = heap.size === 0 ? 0 : heap.peek()[0];
    if (height !== prev) { result.push([x, height]); prev = height; }
  }
  return result;
}

class Heap<T> {
  private a: T[] = [];
  constructor(private before: (x: T, y: T) => boolean) {}
  get size() { return this.a.length; }
  peek(): T { return this.a[0]; }
  push(v: T) {
    const a = this.a;
    a.push(v);
    let i = a.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (!this.before(a[i], a[p])) break;
      [a[i], a[p]] = [a[p], a[i]];
      i = p;
    }
  }
  pop(): T {
    const a = this.a;
    const top = a[0];
    const last = a.pop()!;
    if (a.length) {
      a[0] = last;
      let i = 0;
      for (;;) {
        let m = i;
        const l = 2 * i + 1, r = l + 1;
        if (l < a.length && this.before(a[l], a[m])) m = l;
        if (r < a.length && this.before(a[r], a[m])) m = r;
        if (m === i) break;
        [a[i], a[m]] = [a[m], a[i]];
        i = m;
      }
    }
    return top;
  }
}

vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
    function<vector<vector<int>>(const vector<vector<int>>&, const vector<vector<int>>&)> merge =
        [](const vector<vector<int>>& a, const vector<vector<int>>& b) {
            vector<vector<int>> out;
            size_t i = 0, j = 0; int h1 = 0, h2 = 0;
            while (i < a.size() || j < b.size()) {
                long long xa = i < a.size() ? a[i][0] : LLONG_MAX;
                long long xb = j < b.size() ? b[j][0] : LLONG_MAX;
                long long x = min(xa, xb);
                if (xa == x) h1 = a[i++][1];
                if (xb == x) h2 = b[j++][1];
                int h = max(h1, h2);
                if (out.empty() || out.back()[1] != h) out.push_back({(int)x, h});
            }
            return out;
        };
    function<vector<vector<int>>(int, int)> solve = [&](int lo, int hi) -> vector<vector<int>> {
        if (lo == hi) return {{buildings[lo][0], buildings[lo][2]}, {buildings[lo][1], 0}};
        int mid = (lo + hi) >> 1;
        return merge(solve(lo, mid), solve(mid + 1, hi));
    };
    return buildings.empty() ? vector<vector<int>>{} : solve(0, (int)buildings.size() - 1);
}

public List<List<Integer>> getSkyline(int[][] buildings) {
    return buildings.length == 0 ? new ArrayList<>() : solve(buildings, 0, buildings.length - 1);
}
private List<List<Integer>> merge(List<List<Integer>> a, List<List<Integer>> b) {
    List<List<Integer>> out = new ArrayList<>();
    int i = 0, j = 0, h1 = 0, h2 = 0;
    while (i < a.size() || j < b.size()) {
        long xa = i < a.size() ? a.get(i).get(0) : Long.MAX_VALUE;
        long xb = j < b.size() ? b.get(j).get(0) : Long.MAX_VALUE;
        long x = Math.min(xa, xb);
        if (xa == x) h1 = a.get(i++).get(1);
        if (xb == x) h2 = b.get(j++).get(1);
        int h = Math.max(h1, h2);
        if (out.isEmpty() || out.get(out.size() - 1).get(1) != h) out.add(Arrays.asList((int) x, h));
    }
    return out;
}
private List<List<Integer>> solve(int[][] buildings, int lo, int hi) {
    if (lo == hi) return Arrays.asList(Arrays.asList(buildings[lo][0], buildings[lo][2]), Arrays.asList(buildings[lo][1], 0));
    int mid = (lo + hi) >> 1;
    return merge(solve(buildings, lo, mid), solve(buildings, mid + 1, hi));
}

def get_skyline(buildings):
    def merge(a, b):
        out = []
        i = j = h1 = h2 = 0
        while i < len(a) or j < len(b):
            xa = a[i][0] if i < len(a) else float('inf')
            xb = b[j][0] if j < len(b) else float('inf')
            x = min(xa, xb)
            if xa == x: h1 = a[i][1]; i += 1
            if xb == x: h2 = b[j][1]; j += 1
            h = max(h1, h2)
            if not out or out[-1][1] != h: out.append([x, h])
        return out
    def solve(lo, hi):
        if lo == hi: return [[buildings[lo][0], buildings[lo][2]], [buildings[lo][1], 0]]
        mid = (lo + hi) >> 1
        return merge(solve(lo, mid), solve(mid + 1, hi))
    return [] if not buildings else solve(0, len(buildings) - 1)

function getSkyline(buildings: number[][]): number[][] {
  const merge = (a: number[][], b: number[][]): number[][] => {
    const out: number[][] = [];
    let i = 0, j = 0, h1 = 0, h2 = 0;
    while (i < a.length || j < b.length) {
      const xa = i < a.length ? a[i][0] : Infinity;
      const xb = j < b.length ? b[j][0] : Infinity;
      const x = Math.min(xa, xb);
      if (xa === x) h1 = a[i++][1];
      if (xb === x) h2 = b[j++][1];
      const h = Math.max(h1, h2);
      if (out.length === 0 || out[out.length - 1][1] !== h) out.push([x, h]);
    }
    return out;
  };
  const solve = (lo: number, hi: number): number[][] => {
    if (lo === hi) return [[buildings[lo][0], buildings[lo][2]], [buildings[lo][1], 0]];
    const mid = (lo + hi) >> 1;
    return merge(solve(lo, mid), solve(mid + 1, hi));
  };
  return buildings.length === 0 ? [] : solve(0, buildings.length - 1);
}