Skyline sweep in Python
Sweep over building edges with a max-heap of active heights to output the skyline.
- File
skyline_sweep.py, 32 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/skyline-sweep/. The authors are listed in prov/B8EJVN.jsonl.
import heapq
def get_skyline(buildings: list[list[int]]) -> list[list[int]]:
"""Return the skyline of the buildings as key points [x, h].
Each building is [left, right, height] with left < right and height > 0.
The result is the shortest list of points [x, h], sorted by x, such that
the height of the outline is h on [x, next x) and 0 after the last point.
Two consecutive points never have the same height.
Cost: O(n log n) time and O(n) extra space for n buildings.
"""
xs = sorted({b[0] for b in buildings} | {b[1] for b in buildings}) # @line L1
order = sorted(buildings, key=lambda b: b[0]) # @line L2
heap: list[tuple[int, int]] = [] # @line L3: entries (-height, right)
i = 0
out: list[list[int]] = []
prev = 0
for x in xs: # @line L4
while i < len(order) and order[i][0] == x: # @line L5
heapq.heappush(heap, (-order[i][2], order[i][1])) # @line L6
i += 1
while heap and heap[0][1] <= x: # @line L7
heapq.heappop(heap) # @line L8
h = -heap[0][0] if heap else 0 # @line L9
if h != prev: # @line L10
out.append([x, h]) # @line L11
prev = h
return out # @line L12
test_skyline_sweep.py 68 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/skyline-sweep/. The authors are listed in prov/B8EJVN.jsonl.
import random
from skyline_sweep import get_skyline
def brute_force(buildings: list[list[int]]) -> list[list[int]]:
"""Evaluate f at every integer x and keep the points where it changes."""
if not buildings:
return []
xs = range(min(b[0] for b in buildings), max(b[1] for b in buildings) + 1)
out: list[list[int]] = []
prev = 0
for x in xs:
h = max([b[2] for b in buildings if b[0] <= x < b[1]], default=0)
if h != prev:
out.append([x, h])
prev = h
return out
def test_example() -> None:
b = [[2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8]]
assert get_skyline(b) == [[2, 10], [3, 15], [7, 12], [12, 0], [15, 10], [20, 8], [24, 0]]
def test_edges() -> None:
assert get_skyline([]) == []
assert get_skyline([[1, 5, 3]]) == [[1, 3], [5, 0]]
assert get_skyline([[0, 2, 3], [0, 2, 3], [0, 2, 3]]) == [[0, 3], [2, 0]]
assert get_skyline([[0, 10, 2], [3, 4, 1]]) == [[0, 2], [10, 0]]
big = 2**62
assert get_skyline([[-big, big, big]]) == [[-big, big], [big, 0]]
def test_pitfalls() -> None:
# A start and an end at the same x: no spurious drop to 0.
assert get_skyline([[0, 2, 5], [2, 4, 3]]) == [[0, 5], [2, 3], [4, 0]]
# Adjacent buildings of the same height merge into one piece.
assert get_skyline([[0, 2, 5], [2, 4, 5]]) == [[0, 5], [4, 0]]
# A gap between buildings gives a point at height 0.
assert get_skyline([[0, 2, 5], [3, 4, 5]]) == [[0, 5], [2, 0], [3, 5], [4, 0]]
# Equal left ends with different heights.
assert get_skyline([[0, 2, 3], [0, 1, 4]]) == [[0, 4], [1, 3], [2, 0]]
# Equal right ends with different heights.
assert get_skyline([[0, 3, 3], [1, 3, 4]]) == [[0, 3], [1, 4], [3, 0]]
def test_input_not_changed() -> None:
b = [[5, 6, 1], [1, 2, 1]]
get_skyline(b)
assert b == [[5, 6, 1], [1, 2, 1]]
def test_random_against_brute_force() -> None:
rng = random.Random(4217)
for _ in range(1000):
n = rng.randint(0, 12)
b = []
for _ in range(n):
left = rng.randint(-5, 15)
b.append([left, left + rng.randint(1, 8), rng.randint(1, 6)])
got = get_skyline(b)
assert got == brute_force(b)
assert len(got) <= 2 * n
assert all(got[k][1] != got[k + 1][1] for k in range(len(got) - 1))
What the next level needs
- the tests did not run in this build