public List<int[]> getSkyline(int[][] buildings) {
List<int[]> result = new ArrayList<>();
List<int[]> height = new ArrayList<>();
for(int[] b:buildings) {
height.add(new int[]{b[0], b[2]});
height.add(new int[]{b[1], b[2]});
}
Collections.sort(height, (a, b) > {
if(a[0] != b[0])
return a[0]  b[0];
return a[1]  b[1];
});
Queue<Integer> pq = new PriorityQueue<>((a, b) > (b  a));
pq.offer(0);
int prev = 0;
for(int[] h:height) {
if(h[1] < 0) {
pq.offer(h[1]);
} else {
pq.remove(h[1]);
}
int cur = pq.peek();
if(prev != cur) {
result.add(new int[]{h[0], cur});
prev = cur;
}
}
return result;
}
Short Java solution


Thanks for the good solutions. However, there is a small thing that can be improved. pq.remove() is O(n) hence make it slower. I have modified it a little bit to use TreeMap instead of PriorityQueue and the run time is 2.5X faster.
public class Solution { public List<int[]> getSkyline(int[][] buildings) { List<int[]> heights = new ArrayList<>(); for (int[] b: buildings) { heights.add(new int[]{b[0],  b[2]}); heights.add(new int[]{b[1], b[2]}); } Collections.sort(heights, (a, b) > (a[0] == b[0]) ? a[1]  b[1] : a[0]  b[0]); TreeMap<Integer, Integer> heightMap = new TreeMap<>(Collections.reverseOrder()); heightMap.put(0,1); int prevHeight = 0; List<int[]> skyLine = new LinkedList<>(); for (int[] h: heights) { if (h[1] < 0) { Integer cnt = heightMap.get(h[1]); cnt = ( cnt == null ) ? 1 : cnt + 1; heightMap.put(h[1], cnt); } else { Integer cnt = heightMap.get(h[1]); if (cnt == 1) { heightMap.remove(h[1]); } else { heightMap.put(h[1], cnt  1); } } int currHeight = heightMap.firstKey(); if (prevHeight != currHeight) { skyLine.add(new int[]{h[0], currHeight}); prevHeight = currHeight; } } return skyLine; } }


for those that don't have Java 8, here is another similar solution: https://leetcode.com/discuss/63521/javasolutioniterativelycheckingstartingendingpoints
It uses Comparator to sort the points

hi @jinwu, what is the intuition for this solution? esp. what is the intuition of <left, positive height> and <right, negative height>?

Hi @jinwu, I am wondering why you are using a List to store the height instead of using another PriorityQueue?

I got some explanation here, the mechanism is usually named sweepline. You can image a vertical line sweeping from left to right. https://leetcode.com/discuss/88149/javasolutionusingpriorityqueueandsweepline