Leetcode - The Skyline Problem

[分析]
思路1参考https://leetcode.com/discuss/44537/my-java-ac-code-with-priorityqueues
记录下目前的理解：目标是求出所有拐点。所谓拐点是指让当前x坐标高度发生变化的点，当前x坐标的高度是x处所有楼房的最大高度。所有楼房的左右两顶点加入到考察集合，排序该集合，排序后使用最大堆来保存当前的楼高状态，遍历到左顶点时将高度加入最大堆，右顶点时将高度从最大堆中删除。最大堆堆顶是当前已遍历x坐标的最大高度，一旦堆顶元素变化说明拐点出现了。
各顶点排序规则是若两个点x坐标不同，按x坐标排序，否则需要分三种情况讨论：1）一个是左顶点一个是右顶点，则左顶点排前，考虑case{[0, 1, 1],[1,2,1]},{[0,1,1],[1,2,2]},{[0,1,2],[1,2,1]},也即两栋楼房紧贴在一起的情况，都让左顶点先；2）两个都是左顶点，则高度大的优先；3）两个都是右顶点，则高度小的优先。2）和3）都可考虑case{[1,2,1],[1,2,2],[1,2,3]}来帮助理解，可以想象成高楼套小楼。
思路2参考http://www.meetqun.com/thread-9858-1-1.html
思路3:http://www.geeksforgeeks.org/divide-and-conquer-set-7-the-skyline-problem/

Method 3是第二次做时自己写出来的，一开始边界case仍然没想到，但看到测试样例后修正过来了，最终Accept，很有成就感。

出题者送的话
Be warned, my friend, thou art about to do some serious coding should thou dare this path. Dauntlessly define thy classes and meticulously do thy math. Listen to the prophecy if thou must, but do not let thy own sword idle with rust. By the journey's end, may thy toil and sweat be duly repaid, and no more interviews shalt thou again be afraid.
共勉

// Method 3: mine
public class Solution {
    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> ret = new ArrayList<int[]>();
        if (buildings == null || buildings.length == 0)
            return ret;
        Edge[] edges = getEdges(buildings);
        Arrays.sort(edges, compEdge);
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(comp);
        // Style 2: more clear
        int oldHeight = 0;
        for (int i = 0; i < edges.length; i++) {
            Edge curr = edges[i];
            if (curr.isStart) {
                maxHeap.offer(curr.y);
            } else {
                maxHeap.remove(curr.y);
            }
            int newHeight = maxHeap.isEmpty() ? 0 : maxHeap.peek();
            if (oldHeight != newHeight) {
                oldHeight = newHeight;
                int[] point = {curr.x, newHeight};
                ret.add(point);
            }
        }
        
        //Style 1: mine
        // for (int i = 0; i < edges.length; i++) {
        //     Edge curr = edges[i];
        //     if (curr.isStart) {
        //         if (maxHeap.isEmpty() || curr.y > maxHeap.peek()) {
        //             int[] point = {curr.x, curr.y};
        //             ret.add(point);
        //         }
        //         maxHeap.offer(curr.y);
        //     } else {
        //         if (curr.y == maxHeap.peek()) {
        //             maxHeap.poll();
        //             if (maxHeap.isEmpty() || maxHeap.peek() != curr.y) { // hard point
        //                 int[] point = {curr.x, maxHeap.isEmpty() ? 0 : maxHeap.peek()};
        //                 ret.add(point);
        //             }
        //         } else {
        //             maxHeap.remove(curr.y);
        //         }
        //     }
        // }
        return ret;
    }
    private static class Edge {
        int x, y;
        boolean isStart;
        public Edge(int x, int y, boolean isStart) {
            this.x = x;
            this.y = y;
            this.isStart = isStart;
        }
    } 
    private Comparator<Integer> comp = new Comparator<Integer>() {
        public int compare(Integer a, Integer b) {
            return b - a;
        }  
    };
    private Comparator<Edge> compEdge = new Comparator<Edge>() {
        public int compare(Edge a, Edge b) {
            if (a.x == b.x) { // hard point
                if (a.isStart && b.isStart)
                    return b.y - a.y;
                else if (!a.isStart && !b.isStart)
                    return a.y - b.y;
                else
                    return a.isStart ? -1 : 1;
            } else {
                return a.x - b.x;
            }
        }  
    };
    private Edge[] getEdges(int[][] buildings) {
        Edge[] edges = new Edge[buildings.length * 2];
        int j = 0;
        for (int i = 0; i < buildings.length; i++) {
            edges[j++] = new Edge(buildings[i][0], buildings[i][2], true);
            edges[j++] = new Edge(buildings[i][1], buildings[i][2], false);
        }
        return edges;
    }
}

// Method 1
public class Solution {
    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> result = new ArrayList<int[]>();
        if (buildings == null || buildings.length == 0) return result;
        int N = buildings.length;
        Pair[] pairs = new Pair[2 * N];
        for (int i = 0; i < N; i++) {
            pairs[2 * i] = new Pair(buildings[i][0], -buildings[i][2]);
            pairs[2 * i + 1] = new Pair(buildings[i][1], buildings[i][2]);
        }
        Arrays.sort(pairs);
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(N, Collections.reverseOrder());
        int height = 0;
        for (int i = 0; i < pairs.length; i++) {
            if (pairs[i].height < 0) //left start
                maxHeap.add(-pairs[i].height);
            else //right end
                maxHeap.remove(pairs[i].height);
            int newHeight = !maxHeap.isEmpty() ? maxHeap.peek() : 0;
            if (newHeight != height) {
                height = newHeight;
                int[] point = new int[2];
                point[0] = pairs[i].x;
                point[1] = height;
                result.add(point);
            }
        }
        return result;
    }
    
}
class Pair implements Comparable<Pair>{
    int x;
    int height;
    public Pair(int x, int height) {
        this.x = x;
        this.height = height;
    }
    public int compareTo(Pair p) {
        if (this.x != p.x)
            return this.x - p.x;
        // if the right end and left start overlap, the left start comes first
        if (this.height * p.height < 0) return this.height - p.height;
        // if both left start overlap, the larger height comes first
        if (this.height < 0 && p.height < 0) return Math.abs(p.height) - Math.abs(this.height);
        // if both right end overlap, the smaller height comes first
        return this.height - p.height;
    }
}

// Method 2: 更快些
public class Solution {
  class Node {
    boolean isStart;
    int x;
    int h;
  }

  class NodeComparator implements Comparator<Node> {
    public int compare(Node n1, Node n2) {
      if (n1.x != n2.x) {
        return n1.x - n2.x;
      }
      if (n1.isStart != n2.isStart) {
        return n1.isStart ? -1 : 1;
      }
      if (n1.isStart) {
        return n2.h - n1.h;
      }
      return n1.h - n2.h;
    }
  }

  public List<int[]> getSkyline(int[][] buildings) {
    int n = buildings.length;
    ArrayList<Node> s = new ArrayList<Node>();
    for (int i = 0; i < n; ++i) {
      Node node = new Node();
      node.isStart = true;
      node.x = buildings[i][0];
      node.h = buildings[i][2];
      s.add(node);
      node = new Node();
      node.isStart = false;
      node.x = buildings[i][1];
      node.h = buildings[i][2];
      s.add(node);
    }
    Collections.sort(s, new NodeComparator());

    TreeMap<Integer, Integer> height_map = new TreeMap<Integer, Integer>();
    ArrayList<int[]> result = new ArrayList<int[]>();
    int beginX = 0;
    int curH = 0;
    for (int i = 0; i < s.size(); ++i) {
      Node node = s.get(i);
      if (node.isStart) {
        Integer old = height_map.get(node.h);
        int newValue = 1;
        if (old != null) {
          newValue += old;
        }
        height_map.put(node.h, newValue);
        if (node.h > curH) {
          beginX = node.x;
          curH = node.h;
          result.add(new int[]{beginX, curH});
        }
      } else {
        Integer old = height_map.get(node.h);
        if (old == 1) {
          height_map.remove(node.h);
        } else {
          height_map.put(node.h, old - 1);
        }
        if (height_map.size() == 0) {
          beginX = node.x;
          curH = 0;
          result.add(new int[]{beginX, curH});
        } else {
          Integer h = (int)height_map.lastKey();
          if (h != curH) {
            beginX = node.x;
            curH = h;
            result.add(new int[]{beginX, curH});
          }
        }
      }
    }
    return result;
  }
}