# Question

Formatted question description: https://leetcode.ca/all/218.html

# 218. The Skyline Problem

Hard

## 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. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ].

The output is a list of “key points” (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as: [ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Notes:

• The number of buildings in any input list is guaranteed to be in the range [0, 10000].
• The input list is already sorted in ascending order by the left x position Li.
• The output list must be sorted by the x position.
• 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], ...]

# Algorithm

Save the left and right nodes of each line segment to the new vector height, and sort them according to the x coordinate value.

Then traverse to find the inflection point. When finding the inflection point, use a maximum heap to save the current roof height, * When you encounter the left node, insert the height information in the heap, * The height is deleted from the heap when the node on the right is encountered.

Use pre and cur to represent the previous height and the current height respectively, * When cur != pre, it means that there is an inflection point. * Note that when deleting elements from the heap, I use priority_queue to implement it. Priority_queue does not provide delete operations, so another unordered_map is used to mark the elements to be deleted. * When popping from the heap, first see if it has been marked, * If it has been marked, pop until it is empty or all unmarked values ​​are found. Don’t be careful when sorting externally. * If the x-coordinates of two nodes are the same, we have to consider other attributes of the nodes to order to avoid redundant answers.

    * And the rule of body is
* If they are all left nodes, sort them from largest to smallest according to the y coordinate,
* If they are all right nodes, sort from small to large according to the y coordinate, one left node and one right node, let the left node be in the front


Java