The Skyline Problem

class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        vector<pair<int,int>> events;
        for (auto& b : buildings) {
            events.emplace_back(b[0], -b[2]);       // start (negative height)
            events.emplace_back(b[1],  b[2]);       // end
        }
        sort(events.begin(), events.end());
        multiset<int> heights;
        heights.insert(0);
        int prev = 0;
        vector<vector<int>> ans;
        for (auto& [x, h] : events) {
            if (h < 0) heights.insert(-h);
            else heights.erase(heights.find(h));
            int cur = *heights.rbegin();
            if (cur != prev) {
                ans.push_back({x, cur});
                prev = cur;
            }
        }
        return ans;
    }
};

import (
  "container/heap"
  "sort"
)

type skyHeap struct {
  heights []int
  dead    map[int]int
}

func (h skyHeap) Len() int            { return len(h.heights) }
func (h skyHeap) Less(i, j int) bool  { return h.heights[i] > h.heights[j] }
func (h skyHeap) Swap(i, j int)       { h.heights[i], h.heights[j] = h.heights[j], h.heights[i] }
func (h *skyHeap) Push(x interface{}) { h.heights = append(h.heights, x.(int)) }
func (h *skyHeap) Pop() interface{} {
  o := h.heights
  n := len(o)
  x := o[n-1]
  h.heights = o[:n-1]
  return x
}
func (h *skyHeap) top() int {
  for len(h.heights) > 0 {
    t := h.heights[0]
    if h.dead[t] > 0 {
      h.dead[t]--
      heap.Pop(h)
    } else {
      return t
    }
  }
  return 0
}

func getSkyline(buildings [][]int) [][]int {
  type event struct{ x, h int }
  events := make([]event, 0, 2*len(buildings))
  for _, b := range buildings {
    events = append(events, event{b[0], -b[2]})
    events = append(events, event{b[1], b[2]})
  }
  sort.Slice(events, func(i, j int) bool {
    if events[i].x != events[j].x {
      return events[i].x < events[j].x
    }
    return events[i].h < events[j].h
  })
  pq := &skyHeap{heights: []int{0}, dead: map[int]int{}}
  prev := 0
  var ans [][]int
  for _, e := range events {
    if e.h < 0 {
      heap.Push(pq, -e.h)
    } else {
      pq.dead[e.h]++
    }
    cur := pq.top()
    if cur != prev {
      ans = append(ans, []int{e.x, cur})
      prev = cur
    }
  }
  return ans
}

import heapq
from typing import List

class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        events = []
        for L, R, H in buildings:
            events.append((L, -H, R))  # start: negative height
            events.append((R, 0, 0))   # end marker
        events.sort()
        ans: List[List[int]] = []
        # max-heap of (-height, end_x)
        heap: List[tuple] = [(0, float('inf'))]
        prev = 0
        i = 0
        n = len(events)
        while i < n:
            x = events[i][0]
            while i < n and events[i][0] == x:
                _, neg_h, end = events[i]
                if neg_h < 0:
                    heapq.heappush(heap, (neg_h, end))
                i += 1
            # discard expired tops
            while heap and heap[0][1] <= x:
                heapq.heappop(heap)
            cur = -heap[0][0] if heap else 0
            if cur != prev:
                ans.append([x, cur])
                prev = cur
        return ans

class MaxHeap {
    constructor() { this.h = []; }
    size() { return this.h.length; }
    top() { return this.h[0]; }
    push(x) {
        this.h.push(x);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p][0] >= this.h[i][0]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop() {
        const top = this.h[0];
        const last = this.h.pop();
        if (this.h.length) {
            this.h[0] = last;
            let i = 0;
            const n = this.h.length;
            while (true) {
                let l = i * 2 + 1, r = i * 2 + 2, s = i;
                if (l < n && this.h[l][0] > this.h[s][0]) s = l;
                if (r < n && this.h[r][0] > this.h[s][0]) s = r;
                if (s === i) break;
                [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
                i = s;
            }
        }
        return top;
    }
}

var getSkyline = function(buildings) {
    const events = [];
    for (const [L, R, H] of buildings) {
        events.push([L, -H, R]); // start: negative height
        events.push([R, 0, 0]);  // end marker
    }
    events.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]);
    const heap = new MaxHeap();
    heap.push([0, Infinity]);
    const ans = [];
    let prev = 0;
    let i = 0;
    const n = events.length;
    while (i < n) {
        const x = events[i][0];
        while (i < n && events[i][0] === x) {
            const [, negH, end] = events[i];
            if (negH < 0) heap.push([-negH, end]);
            i++;
        }
        while (heap.size() && heap.top()[1] <= x) heap.pop();
        const cur = heap.size() ? heap.top()[0] : 0;
        if (cur !== prev) {
            ans.push([x, cur]);
            prev = cur;
        }
    }
    return ans;
};

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: negative height
            events.add(new int[]{b[1], 0, 0});        // end marker
        }
        events.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        // max-heap of [height, end_x]
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        heap.offer(new int[]{0, Integer.MAX_VALUE});
        List<List<Integer>> ans = new ArrayList<>();
        int prev = 0;
        int i = 0;
        int n = events.size();
        while (i < n) {
            int x = events.get(i)[0];
            while (i < n && events.get(i)[0] == x) {
                int[] e = events.get(i);
                if (e[1] < 0) heap.offer(new int[]{-e[1], e[2]});
                i++;
            }
            while (!heap.isEmpty() && heap.peek()[1] <= x) heap.poll();
            int cur = heap.isEmpty() ? 0 : heap.peek()[0];
            if (cur != prev) {
                ans.add(Arrays.asList(x, cur));
                prev = cur;
            }
        }
        return ans;
    }
}

class MaxHeap {
    h: number[][] = [];
    size(): number { return this.h.length; }
    top(): number[] { return this.h[0]; }
    push(x: number[]): void {
        this.h.push(x);
        let i: number = this.h.length - 1;
        while (i > 0) {
            const p: number = (i - 1) >> 1;
            if (this.h[p][0] >= this.h[i][0]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop(): number[] {
        const top: number[] = this.h[0];
        const last: number[] = this.h.pop() as number[];
        if (this.h.length) {
            this.h[0] = last;
            let i: number = 0;
            const n: number = this.h.length;
            while (true) {
                let l: number = i * 2 + 1, r: number = i * 2 + 2, s: number = i;
                if (l < n && this.h[l][0] > this.h[s][0]) s = l;
                if (r < n && this.h[r][0] > this.h[s][0]) s = r;
                if (s === i) break;
                [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
                i = s;
            }
        }
        return top;
    }
}

function getSkyline(buildings: number[][]): number[][] {
    const events: number[][] = [];
    for (const [L, R, H] of buildings) {
        events.push([L, -H, R]);
        events.push([R, 0, 0]);
    }
    events.sort((a: number[], b: number[]) => a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]);
    const heap: MaxHeap = new MaxHeap();
    heap.push([0, Infinity]);
    const ans: number[][] = [];
    let prev: number = 0;
    let i: number = 0;
    const n: number = events.length;
    while (i < n) {
        const x: number = events[i][0];
        while (i < n && events[i][0] === x) {
            const [, negH, end] = events[i];
            if (negH < 0) heap.push([-negH, end]);
            i++;
        }
        while (heap.size() && heap.top()[1] <= x) heap.pop();
        const cur: number = heap.size() ? heap.top()[0] : 0;
        if (cur !== prev) {
            ans.push([x, cur]);
            prev = cur;
        }
    }
    return ans;
}