Tap here to switch tabs
Problem
Submissions

Problem: The Skyline Problem

The Skyline Problem gives sorted rectangular buildings with left and right positions and heights. Return outline points where it changes, ending at zero and combining adjacent segments of equal height.

Statement

Imagine standing at a distance, viewing the skyline of a city. The skyline is the shape formed by all the buildings in the city when viewed together. Your task is to determine the shape of this skyline, given all the buildings’ position and height. Each building is represented by three values in the array buildings, where buildings[i]=[lefti, righti, heighti]buildings[i] = [left_i,~right_i,~ height_i]:

  1. lefti is the xx-coordinate where the ithi^{th} building starts.

  2. righti is the xx-coordinate where the ithi^{th} building ends.

  3. heighti is the height of the ithi^{th} building.

All buildings are rectangles that sit on flat ground (height 00). The skyline should be a list of points that define its outline, with each point showing where the height changes as you move from left to right. The final point should have a height of 00, marking where the last building ends.

Note: The output skyline should not have multiple horizontal lines at the same height in a row. For example, an output like [...,[1,4],[3,6],[5,6],[7,6],[8,3],...][...,[1, 4], [3, 6], [5, 6], [7, 6], [8, 3],...] is incorrect. The three lines with height 66 should be combined into one, so the correct version would be [...,[1,4],[3,6],[8,3],...][...,[1, 4], [3, 6], [8, 3],...].

Constraints:

  • 1≤1 \leq buildings.length ≤103\leq 10^3

  • 0≤0 \leq lefti << righti ≤104\leq 10^4

  • 0≤0 \leq heighti ≤104\leq 10^4

  • buildings is sorted by lefti in ascending order.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: The Skyline Problem

The Skyline Problem gives sorted rectangular buildings with left and right positions and heights. Return outline points where it changes, ending at zero and combining adjacent segments of equal height.

Statement

Imagine standing at a distance, viewing the skyline of a city. The skyline is the shape formed by all the buildings in the city when viewed together. Your task is to determine the shape of this skyline, given all the buildings’ position and height. Each building is represented by three values in the array buildings, where buildings[i]=[lefti, righti, heighti]buildings[i] = [left_i,~right_i,~ height_i]:

  1. lefti is the xx-coordinate where the ithi^{th} building starts.

  2. righti is the xx-coordinate where the ithi^{th} building ends.

  3. heighti is the height of the ithi^{th} building.

All buildings are rectangles that sit on flat ground (height 00). The skyline should be a list of points that define its outline, with each point showing where the height changes as you move from left to right. The final point should have a height of 00, marking where the last building ends.

Note: The output skyline should not have multiple horizontal lines at the same height in a row. For example, an output like [...,[1,4],[3,6],[5,6],[7,6],[8,3],...][...,[1, 4], [3, 6], [5, 6], [7, 6], [8, 3],...] is incorrect. The three lines with height 66 should be combined into one, so the correct version would be [...,[1,4],[3,6],[8,3],...][...,[1, 4], [3, 6], [8, 3],...].

Constraints:

  • 1≤1 \leq buildings.length ≤103\leq 10^3

  • 0≤0 \leq lefti << righti ≤104\leq 10^4

  • 0≤0 \leq heighti ≤104\leq 10^4

  • buildings is sorted by lefti in ascending order.