pytudes._2021.leetcode.hard._218__the_skyline_problem

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

Examples:
>>> Solution().getSkyline([])
[]
See Also:

Module Contents

Classes

Solution

Functions

get_skyline(buildings)

Computes a city's skyline formed by all the buildings in a given city.
class pytudes._2021.leetcode.hard._218__the_skyline_problem.Solution[source]
getSkyline(buildings)[source]
Parameters:

buildings (list[list[int]]) –

Return type:

list[list[int]]

pytudes._2021.leetcode.hard._218__the_skyline_problem.get_skyline(buildings)[source]

Computes a city’s skyline formed by all the buildings in a given city.

A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance.

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

Complexity:
n = len(buildings)

Time: O(nlogn) (loop over 2n elements, popping/pushing exactly n elements to a heap during the entire loop) Space: O(n) (2n for the heap and n for the skyline list)

Args:
buildings: locations and heights of all the buildings

in the form buildings[i] = [left_i, right_i, height_i] where:

left_i: x coordinate of the left edge of the ith building. right_i: x coordinate of the right edge of the ith building. height_i: height of the ith building.

Returns: the skyline formed by these buildings collectively.

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.

Constraint(s):
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],…]

Examples:
>>> get_skyline([[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]])
[[2, 10], [3, 15], [7, 12], [12, 0], [15, 10], [20, 8], [24, 0]]
>>> get_skyline([[0,2,3],[2,5,3]])
[[0, 3], [5, 0]]
>>> get_skyline([[1,2,1],[1,2,2],[1,2,3]])
[[1, 3], [2, 0]]
Parameters:

buildings (list[list[int]]) –

Return type:

list[list[int]]