The Skyline Problem
This problem tests the application of priority queue which is implemented with min-heap. Min-heap takes
O(logn) to insert a new node. It takes
O(1) to extract current minimum value and
O(logn) to sort again. With this data structure, I can iterate the boundaries of building in ascending order. My idea is recording all boundaries and associated heights in
priority queue and current existing height in
multiset. Poping out from priority queue for boundaries in ascending order, if the boundary is start boundary, I would insert into the
multiset; if end boundary, I would delete the height from the set. Each time reach the boundaries of building, if current height is different from the previous height, then we can print out the boundary and height.
I ignored a case at first and got WA for several times: Same start boundaries with different heights. For example, in the case of
1 11 5 1 10 5..., if we use
greater comparator for
priority queue, it would sort keys in ascending order; if keys are same, it would sort value in ascending order. Iterating key in ascending order is for the purpose of iterating boundaries, but if the start boundaries are same, we should print the largest height, which should be descending order. Therefore, I customize the comparator: if boundaries are same, make descending order.
Another easy trick: For the purpose of separating start and end boundaries, some people would wrap pair with pair, e.g.
pair<boundary, pair<1 for start and -1 for end, h>>. However, the easier way is
height * 1 for start and
height * -1 for end. Then we can use
pair<boundary, height> to implement it.
Following is the source code in C++:
I don’t know why I get segmentation fault again and again on TIOJ 1202… However, I can get AC on UVa. If you want to take this problem, take care of the output format!