@@ -0,0 +1,2294 @@
+// Solution runs in O(n * log n) time and uses O(n) space, where n is the number of buildings.%0A// Solution is copied from:%0A// https://discuss.leetcode.com/topic/22482/short-java-solution/20%0A//%0A// Idea:%0A// Sweepline is used in solving the problem. List%3Cint%5B%5D%3E %60heights%60 is used to save each of the line%0A// segments including both start and end point. The trick here is to set the start segment as%0A// negative height. This has a few good uses:%0A// - first, make sure the start segment comes before the end one after sorting.%0A// - second, when pushing into the queue, it is very each to distinguish either to add or remove a%0A// segment.%0A// Lastly, when the two adjacent buildings share same start and end x value, the next start segment%0A// always come before due to the negative height, this makes sure that when we peek the queue, we%0A// always get the value we are supposed to get. When the first building is lower, when we peek the%0A// queue, we get the height of the second building, and the first building will be removed in the%0A// next round of iteration. When the second building is lower, the first peek returns the first%0A// building and since it equals to prev, the height will not be added.%0A//%0Aclass Solution %7B%0A  public List%3Cint%5B%5D%3E getSkyline(int%5B%5D%5B%5D buildings) %7B%0A    List%3Cint%5B%5D%3E heights = new ArrayList%3C%3E();%0A    for (int%5B%5D b : buildings) %7B%0A      heights.add(new int%5B%5D%7Bb%5B0%5D, - b%5B2%5D%7D);%0A      heights.add(new int%5B%5D%7Bb%5B1%5D, b%5B2%5D%7D);%0A    %7D%0A    Collections.sort(heights, (a, b) -%3E (a%5B0%5D == b%5B0%5D) ? a%5B1%5D - b%5B1%5D : a%5B0%5D - b%5B0%5D);%0A    TreeMap%3CInteger, Integer%3E heightMap = new TreeMap%3CInteger, Integer%3E(Collections.reverseOrder());%0A    heightMap.put(0, 1);%0A    int prevHeight = 0;%0A    List%3Cint%5B%5D%3E skyLine = new LinkedList%3Cint%5B%5D%3E();%0A    for (int%5B%5D h : heights) %7B%0A      if (h%5B1%5D %3C 0) %7B%0A        Integer cnt = heightMap.get(-h%5B1%5D);%0A        cnt = (cnt == null) ? 1 : cnt + 1;%0A        heightMap.put(-h%5B1%5D, cnt);%0A      %7D else %7B%0A        Integer cnt = heightMap.get(h%5B1%5D);%0A        if (cnt == 1) %7B%0A          heightMap.remove(h%5B1%5D);%0A        %7D else %7B%0A          heightMap.put(h%5B1%5D, cnt - 1);%0A        %7D%0A      %7D%0A      int currHeight = heightMap.firstKey();%0A      if (prevHeight != currHeight) %7B%0A        skyLine.add(new int%5B%5D%7Bh%5B0%5D, currHeight%7D);%0A        prevHeight = currHeight;%0A      %7D%0A    %7D%0A    return skyLine;%0A  %7D%0A%7D%0A

add solution