skyline-sweep-maxheap-lazy-delete

Answer

File: /tmp/skyline/skyline.py — sweep line over sorted critical x-coordinates, max-heap of (-height, right) with lazy deletion:

from heapq import heappush, heappop


def get_skyline(buildings):
    """LeetCode 218: return skyline key points [x, y].

    Sweep line over sorted unique x-coordinates; max-heap of (-height, right)
    with lazy deletion of expired tops. Right edges are exclusive: a building
    [l, r, h] occupies [l, r).
    """
    if not buildings:
        return []

    # All critical x-coordinates (starts and exclusive right ends), sorted.
    xs = sorted({x for l, r, h in buildings for x in (l, r)})

    # Buildings sorted by left edge so we add them in sweep order.
    by_left = sorted(buildings, key=lambda b: b[0])
    heap = []          # (-height, right); min-heap on -height == max-heap on height
    i, n = 0, len(by_left)

    result = []
    last = 0           # previously emitted height

    for x in xs:
        # 1) Activate every building starting at this x.
        while i < n and by_left[i][0] == x:
            l, r, h = by_left[i]
            heappush(heap, (-h, r))
            i += 1

        # 2) Lazy-delete: drop expired tops (right <= x is exclusive => gone).
        while heap and heap[0][1] <= x:
            heappop(heap)

        # 3) Current height is the max of live buildings (0 if none).
        cur = -heap[0][0] if heap else 0

        # 4) Emit only when height actually changes.
        if cur != last:
            result.append([x, cur])
            last = cur

    return result

Why it's correct and O(n log n): - Critical x-coordinates only: every height change happens at a left or right edge, so the ≤ 2n unique xs fully determine the skyline. Sorting dominates at O(n log n). - Lazy deletion is safe: expired entries (whose right <= x, i.e. exclusive end passed) that are not on top cannot be the max-height entry, so they don't distort the answer; they're popped only when they float to the top. Each push/pop is O(log n), total O(n log n). - Simultaneous starts/ends: buildings with the same left are all pushed before computing cur; the top-of-heap check right <= x handles all buildings ending at x in one sweep. - No redundant points: emitting only when cur != last merges equal-height adjacency ([1,5,3], [5,10,3] → [[1,3],[10,0]]) while still keeping a real gap ([1,3,3],[4,6,3] → [3,0],[4,3] are both kept, correctly, since the height genuinely drops to 0 between them). - Final (rightmost_x, 0): at the largest x all buildings have right <= x, so the heap empties and cur becomes 0; since the previous emitted height was > 0, [rightmost_x, 0] is emitted automatically. - Large coordinates: no coordinate indexing, so 10⁹ values are fine — only O(n) heap memory.