I am trying to solve the following problem, but I can't seem to figure out where to start. If anyone could give me a useful insight that would be highly appreciated!

A group of flat-earthers wish to build a group of rectangular houses on an (obviously) completely flat piece of land. When looking at the houses from a distance they form a set of (overlapping) rectangles. The flat-earthers wish to know the complexity of the resulting 2D-skyline. The complexity of the skyline is the number of edges that are part of the border of the union of rectangles, disregarding the border(s) at ground-level. The rectangles comprising the skyline are given as an (unsorted) array of pairs, where the first element is the x-coordinate of the left side of the rectangle, and the second element is the height of the house. (Viewed differently: you could say these are the left-top points of all rectangles.) For example, the houses [(15,4),(5,9),(3,5),(7,7),(1,11),(11,6),(0,8),(13,2)] correspond to a skyline with complexity 16:

Example skyline with complexity 16

Moreover, you know the following about the rectangles:

• Each rectangle has a width of 2.5 meters, but can have any height between 1 meter and n^2 meters.
• The leftmost rectangle's left side has x-coordinate 0.
• Every rectangle has a different x-coordinate and all x-coordinates are integers.
• There is a gap of at most 10 meters between adjacent houses.
• No two houses have the same height.

Describe an algorithm that computes the complexity of the 2D-skyline in O(n) time. Also prove the correctness of your algorithm and analyze its running time.

Does anyone know a good starting point on how to approach this?

CodePudding user response：

This is a standard interview question. The simplest way of looking at it by treating each building as two events:

• At point x, a building of height h starts
• At point x 2.5, a building of height h ends.

You sort these two events and scan them from left to right. You keep track of the building heights that have started but not ended. (Warning: a height must be repeated. Use a list or a multiset.). And you keep track of the largest height. As you scan this list from left to right, you add and delete elements to the building heights. The "current" height changes when the maximum of the current building heights changes.