// 耗时290ms，复杂度O(nlgn+nlgn+n^2)

public List<int[]> getSkyline(int[][] buildings) {

List<int[]> heights = new LinkedList<int[]>();

for (int[] building : buildings) {

heights.add(new int[] {building[0], -building[2]});

heights.add(new int[] {building[1], building[2]});

}

/**

Collections.sort(heights, new Comparator<int[]>() {

@Override

public int compare(int[] o1, int[] o2) {

return o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0];

}

});

Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {

@Override

public int compare(Integer o1, Integer o2) {

return o2 - o1;

}

});

/**

queue.offer(0);

List<int[]> result = new LinkedList<int[]>();

int prev = 0;

for (int[] height : heights) {

if (height[1] < 0) {

queue.add(-height[1]);

} else {

queue.remove(height[1]);

}

int cur = queue.peek();

if (prev != cur) {

result.add(new int[] {height[0], cur});

prev = cur;

}

}

return result;

}

/**

// 耗时50ms，复杂度O(nlgn+nlgn+nlgn)

public List<int[]> getSkyline2(int[][] buildings) {

List<int[]> heights = new LinkedList<int[]>();

for (int[] building : buildings) {

heights.add(new int[] {building[0], -building[2]});

heights.add(new int[] {building[1], building[2]});

}

Collections.sort(heights, new Comparator<int[]>() {

@Override

public int compare(int[] o1, int[] o2) {

return o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0];

}

});

TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>(Collections.<Integer>reverseOrder());

// 这里一定别掉了

map.put(0, 1);

List<int[]> result = new LinkedList<int[]>();

int prev = 0;

for (int[] height : heights) {

if (height[1] < 0) {

map.put(-height[1], map.getOrDefault(-height[1], 0) + 1);

} else {

int cnt = map.getOrDefault(height[1], 0);

if (cnt == 1) {

map.remove(height[1]);

} else {

map.put(height[1], cnt - 1);

}

}

int cur = map.firstKey();

if (prev != cur) {

result.add(new int[] {height[0], cur});

prev = cur;

}

}

return result;

}