Latest content was relocated to https://bintanvictor.wordpress.com. This old blog will be shutdown soon.

Tuesday, October 27, 2015

EPI300 skyline problem

PROBLEM STATEMENT
We have to design a program which helps drawing the skyline of a two-dimensional city given the locations of the rectangular buildings in the city. All of the buildings are built on a flat ground (that is they share a common bottom) and each building Bi is represented by a triplet of (li, ri, hi) where li and ri are the left and right coordinates, respectively, of the ith building, and hi is the height of the building. In the diagram below there are 8 buildings, represented from left to right by the triplets (1, 5, 11), (2, 7, 6), (3, 9, 13), (12, 16, 7), (14, 25, 3), (19, 22, 18), (23, 29, 13) and (24, 28, 4).

Input
The input of the program is a sequence of building triplets. The triplets are sorted by li (the left x-coordinate of the building) in ascending order.

Q1: For any given point X on the x-axis, output the height on the skyline
A1(brute force): Select max(h) from Table where l < x < r. Use an in-memory database.

Q2: draw the skyline. (I think this can benefit from Q1).
A2: Sort all the li and ri individually (8x2 values in our eg.) Each is an Edge struct {
A pointer to the building struct;
bool isLeft, isRight
}
This sorted edges is the array "theEdges".

During the scan, we will maintain a sorted list (skiplist or RB-tree) of "alive" buildings, sorted by height.

Iterate through theEdges,
* If we encounter a left edge, we insert the associated building into "alive". If its height is higher than the currentHeight, then update currentHeight (initialized to 0).
* If we encounter a right edge, we remove the building from "active". If its height == currentHeight, then we update currentHeight by recomputing the highest (among the remaining "alive"), which could be 0, unchanged or a lower height.