# 218 The Skyline Problem

### 218. The Skyline Problem

Hard

• 如果前者小且B2的高度大于B1的高度，则我们将B2的左上顶点也加入skyline中去。
• 如果前者小且B2的高度小于等于B1的高度，则忽略B2的左上顶点

#### 程序代码解释

• liveBuildings代表（左上顶点已经被加入output中但右上顶点还没有做判断的building）的右上顶点的集合，形式为[(height, x-coordinate)…..]
• skyline是output
• 程序里面的这句代码while idx < n and buildings[idx][0] == start:是为了防止有左右坐标完全相同但是height不同的building的存在，it's not useless!!!
• python里面的heapq模块如果有不懂的同学可以看看这个文章：heapq
class Solution(object):
def getSkyline(self, buildings):
"""
:type buildings: List[List[int]]
:rtype: List[List[int]]
"""
idx, n = 0, len(buildings)
liveBuildings, skyline = [], []
while idx < n or len(liveBuildings) > 0: # 只要所有的点没处理完就一直循环
if len(liveBuildings) == 0 or (idx < n and buildings[idx][0] <= -liveBuildings[0][1]):
start = buildings[idx][0]
while idx < n and buildings[idx][0] == start:
heapq.heappush(liveBuildings, [-buildings[idx][2], -buildings[idx][1]])
idx += 1
else:
start = -liveBuildings[0][1]
while len(liveBuildings) > 0 and -liveBuildings[0][1] <= start:
heapq.heappop(liveBuildings)
height = len(liveBuildings) and -liveBuildings[0][0]
if len(skyline) == 0 or skyline[-1][1] != height:
skyline.append([start, height])
return skyline

##### 另外还有一个超级6的大神的代码，但是今天我要赶报告，就只先贴代码了
class Solution(object):
def getSkyline(self, buildings):
"""
:type buildings: List[List[int]]
:rtype: List[List[int]]
"""
events = sorted([(L, -H, R) for L, R, H in buildings] + list(set((R, 0, None) for L, R, H in buildings)))
#events = sorted(event for L, R, H in buildings for event in ((L, -H, R), (R, 0, None)))
res, hp = [[0, 0]], [(0, float("inf"))]
for x, negH, R in events:
while x >= hp[0][1]:
heapq.heappop(hp)
if negH: heapq.heappush(hp, (negH, R))
if res[-1][1] + hp[0][0]:
res += [x, -hp[0][0]],
return res[1:]

public class Solution {
public List<int[]> getSkyline(int[][] buildings) {
List<int[]> result = new ArrayList<int[]>();
if (buildings == null || buildings.length == 0 || buildings[0].length == 0) {
return result;
}

List<Height> heights = new ArrayList<Height>();
for (int[] building : buildings) {
}
Collections.sort(heights, new Comparator<Height>() {
@Override
public int compare(Height h1, Height 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 prev = 0;
for (Height h : heights) {
if (h.height < 0) {
pq.offer(-h.height);
} else {
pq.remove(h.height);
}
int cur = pq.peek();
if (cur != prev) {
prev = cur;
}
}

return result;
}

class Height {
int index;
int height;
Height(int index, int height) {
this.index = index;
this.height = height;
}
}
}


Author: Keqi Huang