the-skyline-problem

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

Algorithms

A city&#39;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 <code>buildings</code> where <code>buildings[i] = [lefti, righti, heighti]</code>:

<ul>
	<li><code>lefti</code> is the x coordinate of the left edge of the <code>ith</code> building.</li>
	<li><code>righti</code> is the x coordinate of the right edge of the <code>ith</code> building.</li>
	<li><code>heighti</code> is the height of the <code>ith</code> building.</li>
</ul>

You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height <code>0</code>.

The skyline should be represented as a list of &quot;key points&quot; sorted by their x-coordinate in the form <code>[[x1,y1],[x2,y2],...]</code>. 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 <code>0</code> and is used to mark the skyline&#39;s termination where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline&#39;s contour.

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

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2020/12/01/merged.jpg" style="width: 800px; height: 331px;" />
<pre>
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.
</pre>

Example 2:

<pre>
Input: buildings = [[0,2,3],[2,5,3]]
Output: [[0,3],[5,0]]
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= buildings.length &lt;= 104</code></li>
	<li><code>0 &lt;= lefti &lt; righti &lt;= 231 - 1</code></li>
	<li><code>1 &lt;= heighti &lt;= 231 - 1</code></li>
	<li><code>buildings</code> is sorted by <code>lefti</code> in&nbsp;non-decreasing order.</li>
</ul>