# LeetCode 218: The Skyline Problem

## Problem Restatement

We are given a list of buildings.

Each building is represented as:

```python
[left, right, height]
```

Meaning:

| Field | Meaning |
|---|---|
| `left` | Left x-coordinate |
| `right` | Right x-coordinate |
| `height` | Building height |

We need to return the skyline formed by these buildings.

The skyline is represented as a list of key points:

```python
[x, height]
```

Each key point means:

```text
at x-coordinate x, the skyline height changes to height
```

The last point must end with height `0`.

The official statement defines the skyline as the outer contour formed by overlapping rectangular buildings and asks for all key points of that contour. ([leetcode.com](https://leetcode.com/problems/the-skyline-problem/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | List of buildings `[left, right, height]` |
| Output | Skyline key points |
| Key point | Position where height changes |
| Final point | Must end with height `0` |

Example function shape:

```python
def getSkyline(buildings: list[list[int]]) -> list[list[int]]:
    ...
```

## Examples

Example 1:

```python
buildings = [
    [2,9,10],
    [3,7,15],
    [5,12,12],
    [15,20,10],
    [19,24,8],
]
```

Output:

```python
[
    [2,10],
    [3,15],
    [7,12],
    [12,0],
    [15,10],
    [20,8],
    [24,0],
]
```

Example 2:

```python
buildings = [[0,2,3],[2,5,3]]
```

Output:

```python
[[0,3],[5,0]]
```

The height remains `3` continuously, so no extra point appears at `x = 2`.

## Understanding the Skyline

Imagine viewing buildings from very far away.

Only the highest visible outline matters.

Example:

```python
[2,9,10]
```

creates:

```text
height 10 from x = 2 to x = 9
```

Now add:

```python
[3,7,15]
```

This taller building hides the previous one between `3` and `7`.

So the skyline becomes:

```text
x = 2 -> height 10
x = 3 -> height 15
x = 7 -> height 10
x = 9 -> height 0
```

The skyline only changes when the maximum active building height changes.

## Key Insight

We process the plane from left to right.

At each x-coordinate:

- some buildings start
- some buildings end

We need to know:

```text
What is the tallest active building right now?
```

That immediately suggests:

| Tool | Purpose |
|---|---|
| Sweep line | Move left to right across x-coordinates |
| Max-heap | Track tallest active building |

## Sweep Line Events

Each building creates two events:

| Event | Meaning |
|---|---|
| Start event | Building becomes active |
| End event | Building stops being active |

For:

```python
[2,9,10]
```

we create:

```text
(2, start, 10)
(9, end, 10)
```

As we sweep through x-coordinates:

- start events add heights
- end events remove heights

The skyline changes whenever the current maximum height changes.

## Heap Challenge

Python only has a min-heap.

To simulate a max-heap, store negative heights.

Example:

```python
heap = [-15, -10, -12]
```

The smallest negative value corresponds to the tallest building.

## Another Challenge: Removing Buildings

Suppose a building ends.

Removing arbitrary values from a heap efficiently is difficult.

Instead, store:

```python
(-height, right)
```

At each x-coordinate:

1. Remove buildings whose `right <= current_x`.
2. The heap top then automatically gives the tallest active building.

This is called lazy deletion.

## Event Representation

For each building:

```python
[left, right, height]
```

create a start event:

```python
(left, -height, right)
```

Why negative height?

Because sorting events should process taller starting buildings first at the same x-coordinate.

End events are handled lazily through heap expiration.

## Algorithm

1. Convert buildings into start events.
2. Sort events by x-coordinate.
3. Maintain a max-heap of active buildings.
4. Sweep through events:
   - remove expired buildings
   - add newly starting buildings
   - compute current maximum height
5. Whenever the height changes, add a skyline key point.

## Walkthrough

Use:

```python
buildings = [
    [2,9,10],
    [3,7,15],
]
```

Events:

```text
(2, -10, 9)
(3, -15, 7)
```

Initial heap:

```python
[(0, inf)]
```

This represents ground level.

### At x = 2

Add building height `10`.

Heap top:

```text
10
```

Skyline changes:

```python
[2,10]
```

### At x = 3

Add building height `15`.

Heap top:

```text
15
```

Skyline changes:

```python
[3,15]
```

### At x = 7

Building `15` expires.

Heap top becomes:

```text
10
```

Skyline changes:

```python
[7,10]
```

### At x = 9

Building `10` expires.

Heap top becomes:

```text
0
```

Skyline changes:

```python
[9,0]
```

Final skyline:

```python
[[2,10],[3,15],[7,10],[9,0]]
```

## Why Event Ordering Matters

Suppose two buildings start at the same x-coordinate:

```python
[2,9,10]
[2,7,15]
```

We must process height `15` first.

Otherwise the skyline might incorrectly produce:

```text
[2,10]
[2,15]
```

instead of directly:

```text
[2,15]
```

Using negative heights naturally sorts taller starts first.

## Correctness

The sweep line processes all x-coordinates where the skyline can possibly change, namely building start positions and effective end positions.

The heap always contains exactly the active buildings whose intervals cover the current x-coordinate. Expired buildings are removed whenever their right endpoint is no longer greater than the current position.

The top of the heap therefore gives the maximum active height at the current x-coordinate.

The skyline changes exactly when this maximum height changes. The algorithm records a key point precisely in that situation.

If the maximum height stays the same, the visible skyline does not change, so no key point is added.

Thus every recorded point is necessary, and every actual skyline height change is recorded.

Therefore the algorithm returns exactly the correct skyline.

## Complexity

Let:

```text
n = number of buildings
```

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n log n)` | Sorting plus heap operations |
| Space | `O(n)` | Events and heap |

Each building is inserted and removed from the heap at most once.

## Implementation

```python
import heapq

class Solution:
    def getSkyline(self, buildings: list[list[int]]) -> list[list[int]]:
        events = []

        for left, right, height in buildings:
            events.append((left, -height, right))

        events.sort()

        result = []

        heap = [(0, float("inf"))]

        prev_height = 0
        i = 0

        while i < len(events):
            current_x = events[i][0]

            while heap and heap[0][1] <= current_x:
                heapq.heappop(heap)

            while i < len(events) and events[i][0] == current_x:
                _, neg_height, right = events[i]
                heapq.heappush(heap, (neg_height, right))
                i += 1

            while heap and heap[0][1] <= current_x:
                heapq.heappop(heap)

            current_height = -heap[0][0]

            if current_height != prev_height:
                result.append([current_x, current_height])
                prev_height = current_height

        return result
```

## Code Explanation

Create building start events:

```python
events.append((left, -height, right))
```

Negative height makes taller buildings sort first.

Sort all events:

```python
events.sort()
```

Initialize the heap with ground level:

```python
heap = [(0, float("inf"))]
```

This prevents the heap from becoming empty.

Before processing the current x-coordinate, remove expired buildings:

```python
while heap and heap[0][1] <= current_x:
    heapq.heappop(heap)
```

Process all events at the same x-coordinate:

```python
while i < len(events) and events[i][0] == current_x:
```

Add buildings to the heap:

```python
heapq.heappush(heap, (neg_height, right))
```

Current skyline height:

```python
current_height = -heap[0][0]
```

If the skyline changed:

```python
if current_height != prev_height:
```

record a new key point:

```python
result.append([current_x, current_height])
```

## Alternative Event-Based Solution

Another common solution explicitly creates both start and end events.

Example:

```python
(left, -height)
(right, height)
```

Then:

- negative height means entering
- positive height means leaving

A multiset or counter structure is needed to remove heights correctly.

This version is elegant in languages with balanced trees, but Python requires more bookkeeping.

The lazy-deletion heap approach is usually simpler in Python.

## Testing

```python
def run_tests():
    s = Solution()

    buildings = [
        [2,9,10],
        [3,7,15],
        [5,12,12],
        [15,20,10],
        [19,24,8],
    ]

    assert s.getSkyline(buildings) == [
        [2,10],
        [3,15],
        [7,12],
        [12,0],
        [15,10],
        [20,8],
        [24,0],
    ]

    assert s.getSkyline([[0,2,3],[2,5,3]]) == [
        [0,3],
        [5,0],
    ]

    assert s.getSkyline([[1,2,1]]) == [
        [1,1],
        [2,0],
    ]

    assert s.getSkyline([[1,5,3],[1,5,5]]) == [
        [1,5],
        [5,0],
    ]

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Standard example | Multiple overlaps |
| Continuous equal height | No redundant key point |
| Single building | Simplest skyline |
| Same start position | Taller building dominates |