> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0218-the-skyline-problem.md).

# 0218. The Skyline Problem

<https://leetcode.com/problems/the-skyline-problem>

## Description

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],...]`

**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.
```

**Example 2:**

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

**Constraints:**

* `1 <= buildings.length <= 104`
* `0 <= lefti < righti <= 231 - 1`
* `1 <= heighti <= 231 - 1`
* `buildings` is sorted by `lefti` in non-decreasing order.

## ac

```java
class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        List<List<Integer>> res  = new ArrayList<>();
        // edge cases
        if (buildings == null || buildings.length == 0) return res;
        
        List<Point> points = new ArrayList<>();
        for (int[] b : buildings) {
            points.add(new Point(b[0], b[2], true)); // start point
            points.add(new Point(b[1], b[2], false)); // end point
        }
        Collections.sort(points);
        
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a); // record heights
        pq.offer(0);  // When there is no building, height is 0.
        int highest = pq.peek();
        
        for (Point p : points) {
            if (p.isStart) {
                // Meet start point, we got a new building, add its height.
                pq.offer(p.height);
            } else {
                // Meet end point, we pass this building, remove its height.
                pq.remove(p.height);
            }
            
            int newHighest = pq.peek();
            if (newHighest != highest) {  
                // The height is changed after we add or remove a building. Record this point.
                res.add(Arrays.asList(p.index, newHighest));
                highest = newHighest;
            }
        }
        
        return res;
    }
    
    class Point implements Comparable<Point> {
        int index;
        int height;
        boolean isStart;
        
        Point(int index, int height, boolean isStart) {
            this.index = index;
            this.height = height;
            this.isStart = isStart;
        }
        
        @Override
        public int compareTo(Point other) {
            if (this.index == other.index) {
                int thisHeight = this.height;
                // This is tricky: if these are same start points, handle heighest first.
                // If they are end points, handle lowest first. 
                // Becase if we remove heighest, the heigh changed and we record a point we don't want.
                // example: [[4,9,10],[4,9,15],[4,9,12]]
                // So, for all points in the same index, the process order is: high->low start points, then low->high end points
                if (this.isStart) {
                    if (other.isStart) {
                        return other.height - this.height; // Descending height for start points
                    } else {
                        return -1; // always handle start point first
                    }
                } else {
                    if (other.isStart) {
                        return 1; // always handle start point first
                    } else {
                        return this.height - other.height; // Ascending height for end points
                    }
                }
            } 
            
            return this.index - other.index;
        }
    }
}

// O(NlogN) time, O(N) space
// The key is to record the point when height is changed after we add or remove a building. The tricky part is the ordering for all points in the same index.
```