# Java solution using hash-heap, 32ms

• I write the explanation in the comment of code. The time complexity is O(n logn). (If you delete all the comments, the time may be less than 30ms : ) )

``````public class Solution {
public class HashHeap {
ArrayList<Integer> heap;
HashMap<Integer,Node> hashmap;

public class Node {
int id;
int num;    // number of same integers
public Node(int id, int num) {
this.id = id;
this.num = num;
}
}

public HashHeap() {
heap = new ArrayList<Integer>();
hashmap = new HashMap<Integer,Node>();
}

public int peek() {
if (heap.size() > 0) return heap.get(0).intValue();
else return 0;
}

// if the hashmap already contains the height(height is not unique, so this is possible), update the num of such height
if (hashmap.containsKey(height)) {
hashmap.put(height, new Node(hashmap.get(height).id, hashmap.get(height).num+1));
return;
}
int id = heap.size()-1;
while (parent(id) > -1) {
int parentId = parent(id);
if (heap.get(id) > heap.get(parentId)) {
// swap two heights
swap(id, parentId);
// update hashmap
hashmap.put(heap.get(id), new Node(id, 1));
// update id
id = parentId;
} else {
break;
}
}
// final update
hashmap.put(heap.get(id), new Node(id, 1));
}

public void delete(Integer height) {
// if num of the height is bigger than 1(height is not unique, so this is possible), just update the num of such height
if (hashmap.get(height).num > 1) {
hashmap.put(height, new Node(hashmap.get(height).id, hashmap.get(height).num-1));
return;
}
// else delete the height
int id = hashmap.get(height).id;
// swap two heights
swap(id, heap.size()-1);
hashmap.put(heap.get(heap.size()-1), new Node(heap.size()-1, 1));
hashmap.put(heap.get(id), new Node(id, 1));
// while left child's id is less than last id
while (id*2+1 < heap.size()-1) {
// if left child has bigger height or right child is last node
int son;
if (heap.get(id*2+1) > heap.get(id*2+2) || (id*2+2) == (heap.size()-1)) {
son = id*2+1;
} else {
son = id*2+2;
}
// if son's height is bigger, then swap
if (heap.get(son) > heap.get(id)) {
swap(son, id);
hashmap.put(heap.get(son), new Node(son, 1));
hashmap.put(heap.get(id), new Node(id, 1));
id = son;
} else {
hashmap.put(heap.get(id), new Node(id, 1));
break;
}
}
hashmap.remove(heap.get(heap.size()-1));
heap.remove(heap.size()-1);
}

public int parent(int id) {
return (id-1)/2;
}

public void swap(int a, int b) {
Integer temp = heap.get(a);
heap.set(a, heap.get(b));
heap.set(b, temp);
}
}

public class Edge {
int index;
int height;
boolean left;
public Edge(int index, int height, boolean left) {
this.index = index;
this.height = height;
this.left = left;
}
}

// Used for searching through hashmap
public class Height {
int index;
int height;
public Height(int index, int height) {
this.index = index;
this.height = height;
}
}

public List<int[]> getSkyline(int[][] buildings) {
// Solution: use a max heap to store the heights of buildings
//           add the height when reaches the left edge, and delete it when reaches the right edge
//           if the current height changes, add the point to final list
//           use hash heap to reduce time complextity
List<int[]> ret = new ArrayList<int[]>();
// number of buildings
int n = buildings.length;
if (n == 0) return ret;
Edge[] buildingNodes = new Edge[2*n];
for (int i=0; i<n; i++) {
buildingNodes[2*i] = new Edge(buildings[i][0], buildings[i][2], true);
buildingNodes[2*i+1] = new Edge(buildings[i][1], buildings[i][2], false);
}
// Sort by node.index
Arrays.sort(buildingNodes, new Comparator<Edge>() {
public int compare(Edge a, Edge b) {
// if index is the same
if (a.index == b.index) {
// all the right edges go before left edges
// all the right edges go from short to tall
// all the left edges go from tall to short
if (a.left == false) {
if (b.left == true) {
return -1;
} else {
return a.height - b.height;
}
} else {
if (b.left == false) {
return 1;
} else {
return b.height - a.height;
}
}
} else {
return a.index - b.index;
}
}
});
HashHeap heap = new HashHeap();
int prevHeight = 0;
for (int i=0; i<2*n; i++) {
if (buildingNodes[i].left) {
} else {
heap.delete(buildingNodes[i].height);
}
int height = heap.peek();
if (height != prevHeight) {
int[] point = new int[]{buildingNodes[i].index, height};
// check the prev pair's index part
if (ret.size() >0 && ret.get(ret.size()-1)[0] == buildingNodes[i].index) {
// if previous one is right, this one is left and their heights are the same
if (buildingNodes[i-1].left == false && buildingNodes[i].left == true && buildingNodes[i].height == buildingNodes[i-1].height) {
ret.remove(ret.size()-1);
} else {
ret.set(ret.size()-1, point);
}
} else {