题目:
题解:
class Solution {
public List<List<Integer>> getSkyline(int[][] buildings) {
PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> b[1] - a[1]);
List<Integer> boundaries = new ArrayList<Integer>();
for (int[] building : buildings) {
boundaries.add(building[0]);
boundaries.add(building[1]);
}
Collections.sort(boundaries);
List<List<Integer>> ret = new ArrayList<List<Integer>>();
int n = buildings.length, idx = 0;
for (int boundary : boundaries) {
while (idx < n && buildings[idx][0] <= boundary) {
pq.offer(new int[]{buildings[idx][1], buildings[idx][2]});
idx++;
}
while (!pq.isEmpty() && pq.peek()[0] <= boundary) {
pq.poll();
}
int maxn = pq.isEmpty() ? 0 : pq.peek()[1];
if (ret.size() == 0 || maxn != ret.get(ret.size() - 1).get(1)) {
ret.add(Arrays.asList(boundary, maxn));
}
}
return ret;
}
}