Advanced Graph Algorithms→ Disjoint-set datastructure (union-find)→ Advertising hoardings
Downtown Siruseri is booming and the main road is now lined with a continuous row of skyscrapers. For aesthetic reasons, the Siruseri Municipal Corporation had banned advertising hoardings along the main road.
The High Court has squashed the Municipal Corporation's ban as unconstitutional and ruled that rectangular hoardings may be put up parallel to the main road, along the walls of the skyscrapers lining the road. The only restriction is that a hoarding may not extend above the height of any building along its length.
Advertising agencies across the city are buzzing witth excitement at the news and accounts executives are busy calculating how large they can make their hoardings, in terms of total area, to collect maximum revenue from advertisers.
For instance suppose the Siruseri skyline appears as follows, where the number at the top of each building specifies its height while the number at the bottom of each building specifies its width, both quantities measured in metres.
80
70 ---------
--------- 55 | |
50 | | 50 ------| |
---| |------ | | | 40
30 | | | | | | |------
------| | | | | | | |
| | | | |10 | | | |
| | | | |---| | | |
| | | | | | | | |
===========================================================
20 10 30 20 10 20 30 20
In this situation, the biggest legal hoarding spans the second, third and fourth buildings with an area of 60 × 50 = 3000 square metres. The next best possibility is a hoarding of 70 × 40 = 2800 square metres, spanning the last three buildings.
Your task is to compute the maximum area that a hoarding can have for a given arrangement of skyscrapers.
Solution
The largest rectangle will be as tall as the shortest building it covers. Otherwise, we could increase its height. For each building height, we need to find the widest rectangle of that height. In other words, we want to compute the longest segment of buildings of that height or less.
We partition the buildings into segments. Initially each building is a segment of length 1.
We process the buildings in decreasing order of height as follows. For each building, if it is shorter than the building on its left, merge it with the segment on its left. Likewise, if it is shorter than the building on its left, merge it with the segment on its right.
Since we are processing buildings in decreasing order of height, the segments to the left and right that we merge with will not contain any buildings shorter than the current building and will have on their outer boundary a building that is equal to or shorter than the current building.
We maintain the width and height of each segment and update it when we create a new segment. While doing this, we also maintain and update the size of the maximum rectangle seen so far.
Use the union-find data structure to keep track of segments efficiently.