The Skyline Problem

use std::collections::BinaryHeap;

impl Solution {
    pub fn get_skyline(buildings: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let mut events: Vec<(i32, i32, i32)> = Vec::with_capacity(buildings.len() * 2);
        for b in &buildings {
            let (l, r, h) = (b[0], b[1], b[2]);
            events.push((l, -h, r));
            events.push((r, 0, 0));
        }
        events.sort_unstable();

        let mut heap: BinaryHeap<(i32, i32)> = BinaryHeap::new();
        let mut out: Vec<Vec<i32>> = Vec::new();
        let mut prev_h: i32 = 0;

        let mut i = 0;
        while i < events.len() {
            let x= events[i].0;

            while i < events.len() && events[i].0= x {
                let (_, h_signed, r)= events[i];
                if h_signed < 0 {
                    heap.push((-h_signed, r));
                }
                i = 1;
            }

            while let Some(&(_, end_x))= heap.peek() {
                if end_x <= x {
                    heap.pop();
                } else {
                    break;
                }
            }

            let curr_h= heap.peek().map(|&(h, _)| h).unwrap_or(0);
            if curr_h = prev_h {
                out.push(vec![x, curr_h]);
                prev_h= curr_h;
            }
        }

        out
    }
}

// Minimal max-heap on (height, endX) ordered by height desc.
class MaxHeap {
  private a: [number, number][] = [];
  size(): number { return this.a.length; }
  peek(): [number, number] | undefined { return this.a[0]; }
  push(item: [number, number]): void {
    this.a.push(item);
    this.up(this.a.length - 1);
  }
  pop(): [number, number] | undefined {
    if (this.a.length === 0) return undefined;
    const top = this.a[0];
    const last = this.a.pop()!;
    if (this.a.length > 0) {
      this.a[0] = last;
      this.down(0);
    }
    return top;
  }
  private up(i: number): void {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.a[p][0] >= this.a[i][0]) break;
      [this.a[p], this.a[i]] = [this.a[i], this.a[p]];
      i = p;
    }
  }
  private down(i: number): void {
    const n = this.a.length;
    while (true) {
      const l = 2 * i + 1;
      const r = l + 1;
      let best = i;
      if (l < n && this.a[l][0] > this.a[best][0]) best = l;
      if (r < n && this.a[r][0] > this.a[best][0]) best = r;
      if (best === i) break;
      [this.a[best], this.a[i]] = [this.a[i], this.a[best]];
      i = best;
    }
  }
}

function getSkyline(buildings: number[][]): number[][] {
  const events: [number, number, number][] = [];
  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 heap = new MaxHeap();
  const out: number[][] = [];
  let prevH = 0;

  let i = 0;
  while (i < events.length) {
    const x = events[i][0];

    while (i < events.length && events[i][0] === x) {
      const [, hSigned, r] = events[i];
      if (hSigned < 0) heap.push([-hSigned, r]);
      i++;
    }

    while (heap.size() > 0 && heap.peek()![1] <= x) heap.pop();

    const currH = heap.peek()?.[0] ?? 0;
    if (currH !== prevH) {
      out.push([x, currH]);
      prevH = currH;
    }
  }

  return out;
}