# 2 Java Solutions, one of which is short and fast; the other is easy to understand

• Solution 1, referring this post.
Complexity: O(nlogn) time, O(n) space

``````    public List<int[]> getSkyline(int[][] buildings) {
List<int[]> outline = new ArrayList<>();
List<int[]> edges = new ArrayList<>();
for (int[] b : buildings) {
}
Collections.sort(edges, (int[] b1, int[] b2) -> {
if (b1[0] != b2[0]) return b1[0] - b2[0];
return b1[1] - b2[1];
});
TreeMap<Integer, Integer> q = new TreeMap<>(Collections.reverseOrder());
int preH = 0;
q.put(0, 1);
for (int[] e : edges) {
if (e[1] < 0) q.put(-e[1], q.getOrDefault(-e[1], 0) + 1);
else {
if (q.get(e[1]) == 1) q.remove(e[1]);
else q.put(e[1], q.get(e[1]) - 1);
}
int newH = q.firstKey();
if (newH != preH) {
preH = newH;
}
}
return outline;
}
``````

Another solution, which is longer but more straightforward in algorithm:
Complexity: O(n^2) time (due to the O(n) time cost of PriorityQueue.remove()), O(n) space. The time cost can be reduced to O(nlogn) by replacing PriorityQueue with TreeMap. However I keep using PriorityQueue to make this solution easy to understand.

``````private class Edge implements Comparable<Edge> {
int x, h;
Boolean isLeft;
public Edge(int x, int h, Boolean isLeft) {
this.x = x;
this.h = h;
this.isLeft = isLeft;
}
@Override
public int compareTo(Edge e) {
if (x != e.x) return x - e.x;
if (isLeft != e.isLeft) return e.isLeft.compareTo(isLeft);
if (isLeft) return e.h - h;
else return h - e.h;
}
}
public List<int[]> getSkyline(int[][] buildings) {
List<int[]> outline = new ArrayList<>();
if (buildings == null || buildings.length == 0) return outline;
Map<Edge, Edge> lefts = new HashMap<>();
List<Edge> edges = new ArrayList<>();
for (int i = 0; i < buildings.length; ++i) {
int[] b = buildings[i];
Edge left = new Edge(b[0], b[2], true);
Edge right = new Edge(b[1], b[2], false);
lefts.put(right, left);
}
Collections.sort(edges);

Queue<Edge> q = new PriorityQueue<>(2 * buildings.length, (Edge e1, Edge e2) -> e2.h - e1.h);
for (Edge edge : edges) {
int preH = 0;
if (q.size() > 0) preH = q.peek().h;
if (!edge.isLeft) q.remove(lefts.get(edge));
else q.offer(edge);
int newH = 0;
if (q.size() > 0) newH = q.peek().h;
if (newH != preH) outline.add(new int[]{edge.x, newH});
}
return outline;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.