> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# The Skyline Problem Python Solution with Tests

> Tested Python solution for LeetCode 218 with 19 pytest cases. Generate a practice environment with lcpy.

LeetCode 218, [Hard](/catalog/hard). Topics: [Array](/catalog/topics/array), [Divide and Conquer](/catalog/topics/divide-and-conquer), [Binary Indexed Tree](/catalog/topics/binary-indexed-tree), [Segment Tree](/catalog/topics/segment-tree), Sweep Line, [Sorting](/catalog/topics/sorting), [Heap (Priority Queue)](/catalog/topics/heap-priority-queue), [Ordered Set](/catalog/topics/ordered-set). [View on LeetCode](https://leetcode.com/problems/the-skyline-problem/description/).

Generate this problem as a practice environment: tested reference solution, 19 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 218   # by problem number
lcpy gen -s the_skyline_problem   # by problem name
```

## Problem

A city's **skyline** is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Given the locations and heights of all the buildings, return the skyline formed by these buildings collectively.

The geometric information of each building is given in the array `buildings` where `buildings[i] = [lefti, righti, heighti]`:

* `lefti` is the x coordinate of the left edge of the `ith` building.
* `righti` is the x coordinate of the right edge of the `ith` building.
* `heighti` is the height of the `ith` building.

You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height `0`.

The skyline should be represented as a list of "key points" sorted by their x-coordinate in the form `[[x1,y1],[x2,y2],...]`. Each key point is the left endpoint of some horizontal segment in the skyline except the last point in the list, which always has a y-coordinate `0` and is used to mark the skyline's termination where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline's contour.

**Note:** There must be no consecutive horizontal lines of equal height in the output skyline. For instance, `[...,[2 3],[4 5],[7 5],[11 5],[12 7],...]` is not acceptable; the three lines of height 5 should be merged into one in the final output as such: `[...,[2 3],[4 5],[12 7],...]`

### Examples

![Example 1](https://assets.leetcode.com/uploads/2020/12/01/merged.jpg)

```
Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
```

**Explanation:** Figure A shows the buildings of the input. Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.

```
Input: buildings = [[0,2,3],[2,5,3]]
Output: [[0,3],[5,0]]
```

### Constraints

* `1 <= buildings.length <= 10^4`
* `0 <= lefti < righti <= 2^31 - 1`
* `1 <= heighti <= 2^31 - 1`
* `buildings` is sorted by `lefti` in non-decreasing order.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/the_skyline_problem/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/the_skyline_problem/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
import heapq


class Solution:
    # Time: O(n log n)
    # Space: O(n)
    def get_skyline(self, buildings: list[list[int]]) -> list[list[int]]:
        events: list[tuple[int, int, int]] = []
        for left, right, height in buildings:
            events.append((left, -height, right))
            events.append((right, 0, 0))
        events.sort()

        heap: list[tuple[int, int]] = [(0, 2**31)]
        result: list[list[int]] = []
        for x, neg_height, right in events:
            while heap[0][1] <= x:
                heapq.heappop(heap)
            if neg_height < 0:
                heapq.heappush(heap, (neg_height, right))
            height = -heap[0][0]
            if not result or result[-1][1] != height:
                result.append([x, height])
        return result
```

## Complexity

| Time | Space |
| - | - |
| O(n log n) | O(n) |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.