Programming challenge #2

by Charles Bovaird

Skyline problem

Write a program to solve this problem.

Suppose you are given a series of rectangular boxes laid along the positive x-axis. Each box is defined by 3 integer numbers; a left x value, a height along the y-axis, and a right x value. For example one triple might be (1 11 5), meaning that the box extends horizontally from x=l to x=5, with a height on the y-axis of 11 units. The rectangular boxes may overlap or intersect as well as stand-alone. For example, the three boxes represented by (1 11 5), (2 6 7) and (3 13 9) represent two intersecting boxes, (1 11 5) (3 13 9) and one completely subsumed one (2 6 7).

You are expected to create a program called Skyline, which will produce the outline of the boxes, eliminating hidden boxes and intersections from any triplet sequence.

The result should be, essentially, a skyline, a simple sequence of integers consisting of the leftmost starting x value, followed by the associated height, followed in turn by the x value, with its associated height. This continues alternating x values and y heights until the sky outline is completed.

You may assume that the left x values (the starting values for each box in its triplet) are given in ascending order.

Illustrate the following test Case:

Let an LHR triplets be (1 11 5) (2 6 7) (3 13 9) (12 7 16) (14 3 25) (19 18 22).

The skyline result should be: (1 11 3 13 9 0 12 7 16 3 19 18 22 3 25)

State clearly which language and version has been used. Send solutions to treasurer@dacs.org

Correct solutions and authors will be published.