The Skyline Problem(Hard)
题目大意：
一座城市的天际线是指从远处观察城市，所有建筑侧影的外部轮廓。现在假设给定所有建筑的位置和高度，如城市景观照片（图A）所示，编写程序输出这些建筑形成的天际线（图B）。
每一座建筑的地理信息由一个整数三元组 [Li, Ri, Hi] 指定， 其中Li 与 Ri分别是第i座城市的左右边缘，Hi为其高度。题目保证 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, 并且 Ri - Li > 0。你可以假设所有的建筑都是完美的矩形，位于一个绝对平坦且高度为0的平面之上。
例如，图A中所有建筑的坐标是：[ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] 。
输出是一列可以唯一标识天际线的“关键点”（图B中的红点），形如 [ [x1,y1], [x2, y2], [x3, y3], ... ] 。关键点是指水平线段的左端点。注意最后一个关键点，即城市边缘的最右端，仅仅是用来标识天际线的终点，其高度永远为0。并且，任意两个相邻建筑之间的平地也应视为天际线的一部分。
例如，图B的天际线应该表示为：[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ]。
注意：
任意输入的建筑物总数在范围[0, 10000]之内
输入的列表是按照位置Li的左端点递增有序的。
输出列表必须按照x坐标排序。
在天际线中不可以存在连续的等高水平线段。例如，[...[2 3], [4 5], [7 5], [11 5], [12 7]...] 是不正确的；其中的三条线段高度均为5，因此应该合并输出为： [...[2 3], [4 5], [12 7], ...]
解题思路： Construct a HeightLine class to store each edge, with height < 0 indicating the left edge, height > 0 indicating the right edge.
Sort the edges by index and height, the tricky part is when h1.index == h2.index, we have three cases:
- h1 and h2 are both left edge (height < 0): the higher line should be sorted before the lower line (for e.g., |h1.height| > |h2.height| => h1.height – h2.height < 0 => h1 will be sorted before h2)
- h1 and h2 are both right edge (height >0): the lower line should be sorted before the higher line (for e.g., h1.height – h2.height < 0 => h1 will be sorted before h2)
- One left edge (<0) and="" one="" right="" edge="" (="">0): left should be sorted before right (for e.g., h1 is left and h2 is right => h1.height – h2.height < 0 => h1 will be sorted before h2)
- Thus we can safely use h1.height – h2.height as the return value of compare() function
Offer / Delete the sorted edges one by one into a Max-heap, which store the heights of all the valid buildings to the current index. Check if offering / deleting a new edge will update the peek(): if it is, we find a new skyline and add it to the result.
class HeightLine {
int height; //negative if it is the left height line; positive if it is the right height line
int index;
public HeightLine(int index, int height) {
this.index = index;
this.height = height;
}
}
public List<int[]> getSkyline(int[][] buildings) {
List<int[]> result = new ArrayList<int[]>();
if (buildings == null) {
return result;
}
List<HeightLine> heights = new ArrayList<HeightLine>();
for (int[] building : buildings) {
HeightLine lh = new HeightLine(building[0], -building[2]); // left height line
HeightLine rh = new HeightLine(building[1], building[2]); // right heightline
heights.add(lh);
heights.add(rh);
}
Collections.sort(heights, new Comparator<HeightLine>(){ // sort ascendingly
@Override
public int compare(HeightLine h1, HeightLine h2) {
return h1.index != h2.index ? h1.index - h2.index : h1.height - h2.height;
}
});
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(1000, Collections.reverseOrder());
pq.offer(0);
int preMax = 0;
for (HeightLine h : heights) {
if (h.height < 0) { // left height line
pq.offer(-h.height);
} else {
pq.remove(h.height);
}
int curMax = pq.peek();
if (curMax != preMax) {
result.add(new int[]{h.index, curMax});
preMax = curMax;
}
}
return result;
}
public static void main(String[] strs) throws Exception{
//[Li, Ri, Hi], where Li and Ri are the x coordinates of the left
// and right edge of the ith building, respectively, and Hi is its height.
int arr[][] = {{1, 5, 11}, {2, 7, 6}, {3, 9, 13},
{12, 16, 7}, {14, 25, 3}, {19, 22, 18},
{23, 29, 13}, {24, 28, 4}};
/*int arr[][] = {{2,9,10}, {3, 7, 15}, {5, 12, 12},
{15, 20, 10}, {19, 24, 8}};*/
//int arr[][] = {{1,5,11},{1,6,13}};
SkyLine instance = new SkyLine();
System.out.println(instance.getSkyline2(arr));
}
References
2 [LeetCode]The Skyline Problem