#218
The Skyline Problem
candidate master · 1560 · lc hard +32 · verified · 45% accepted · 6,207 likes · top 28%
Description
The skyline of a city outlines the silhouette its buildings form when seen from afar. Given rectangular building footprints and heights, compute that silhouette.
Building i is described by buildings[i] = [lefti, righti, heighti]:
- lefti — x-coordinate of its left wall.
- righti — x-coordinate of its right wall.
- heighti — its height.
All buildings sit at ground level (height 0). Return skyline key points [[x1,y1],...] sorted by x. Each point marks the start of a horizontal segment; the final point always has height 0. No two consecutive segments may share the same height.
Example 1:
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]]
Code
1
2
3