A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).
解题思路：
本题如果一个矩形一个矩形的加入，涉及到回溯问题，比较复杂。
一个简便的思路是，根据横坐标排序，然后遍历求拐点。求拐点的时候用一个最大化heap来保存当前的楼顶高度，遇到左边节点，就在heap中插入高度信息，遇到右边节点就 从heap中删除高度。分别用pre与cur来表示之前的高度与当前的高度，当cur != pre的时候说明出现了拐点。JAVA实现如下：
static public List<int[]> getSkyline(int[][] buildings) {
List<int[]> res = new ArrayList<int[]>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(11,
new Comparator<Integer>() {
public int compare(Integer a, Integer b) {
return b - a;
}
});
List<int[]> bl = new ArrayList<int[]>();
for (int i = 0; i < buildings.length; i++) {
bl.add(new int[] { buildings[i][0], buildings[i][2] });
bl.add(new int[] { buildings[i][1], -buildings[i][2] });
}
Collections.sort(bl, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];
}
});
int pre = 0, cur = 0;
for (int i = 0; i < bl.size(); i++) {
int[] b = bl.get(i);
if (b[1] > 0) {
maxHeap.add(b[1]);
cur = maxHeap.peek();
} else {
maxHeap.remove(-b[1]);
cur = (maxHeap.peek() == null) ? 0 : maxHeap.peek();
}
if (cur != pre) {
res.add(new int[] { b[0], cur });
pre = cur;
}
}
return res;
}