UVa 105

From Algorithmist
Jump to: navigation, search

105 - The Skyline Problem[edit]

Summary[edit]

This problem has an easy solution due to the constraints. Since the buildings lies between 0 and 10,000 inclusively, using a height map should suffice. Alternatively, performing a sweep line on the buildings will give a faster, though more difficult to implement, solution.

Bruteforce Explanation[edit]

We can use an array of 10,000 elements to represent the height of each individual discrete x-coordinate. For each x-coordinate, we take the highest of all the heights of all the buildings within the range. For each adjacent x-coordinates, report if there is a change in the height.

At one point, there were trick cases with negative coordinates, but it's been corrected since.

Bruteforce Gotcha's[edit]

  • Negative coordinates.

Sweep Line Explanation[edit]

Sweep a vertical line from (-\infty ,\infty ). Maintain the intersection of the buildings with the sweep line in a balanced search tree named T. There are two kinds of events, which are kept in a priority queue Q.

  • insertion events - keyed by the left end of a building
    • insert the height of the new building into T
    • insert a removal event for the right end of the building into Q.
  • removal events - keyed by the right end of a building
    • remove the corresponding building height from T

As the event e is processed from Q, make all the status modifications for each event having the same key as e, then determine the maximum height of the buildings with a single query to T. Like in the brute force approach, report only changes in the height, even if distinct buildings have the same height.

The total cost of the algorithm is O(n\log n). There are exactly 2n events, one event for each of the n left ends of the buildings, and one event for each of the n right ends of the buildings. To process each event, it costs O(\log n) to extract the minimum from Q, O(\log n) for an insertion or deletion in T, and O(\log n) for each maximum query in T. Thus the cost of processing each event is O(\log n), for a total cost of O(n\log n)

There are a few advantages of the sweep line algorithm. In the brute force approach, doubling the width of the buildings will double the runtime cost. With the sweep line algorithm, doubling the width of the buildings will not change the running time. Also, the Sweep Line algorithm will work if the input is not discrete, whereas the heightmap approach requires integer coordinates.

Sweep Line Gotcha's[edit]

  • The start and end points of buildings may share an x-coordinate. Make sure to process all events with the same x-coordinate before making a decision about the building height at the given coordinate.

Input[edit]

1 11 5
1 20 6
2 6 7
3 13 9
12 7 16
14 3 25
15 8 16
19 18 22
23 13 29
24 4 28

Output[edit]

1 20 6 13 9 0 12 7 15 8 16 3 19 18 22 3 23 13 29 0

Solution[edit]