# Java AC solution with comments

• Just like the solution said

1. sort the edges, x first, height next (decreasing order), put left edges first
2. for left edge, put to heap. output key point if the top of this edge is the highest point so far. output (edge.x, edge.y)
3. if it's right edge, remove it from heap. output key point if current max height in heap is different from the last output (so that we don't output points on the same horizontal line). if so, output key point
(right edge.x, max height)
4. i had special treatment on last point- we need to see if there is any "pending key point" which will lead to horizontal lines with len=0

also the java implementation of heap has remove(object) but since it traverse the array to find value i dont think it's O logn

``````public class Solution {
private class Edge {
// start form x,0 to x,y
private int x;
private int y;
// left edge or not
private boolean isStart;

private Edge(int x, int y, boolean isStart) {
this.x = x;
this.y = y;
this.isStart = isStart;
}
@Override
public String toString() {
return "Edge [x=" + x + ", y=" + y + ", isStart=" + isStart + "]";
}
}

public List<int[]> getSkyline(int[][] buildings) {
List<Edge> edges = parseEdges(buildings);
edges.sort((o1, o2) -> {
if (o1.x != o2.x) {
// first sort by x
return o1.x - o2.x;
} else {
if(o1.y!=o2.y){
// if x is the same, we put higher ones at the front
return o2.y-o1.y;
}
if (o1.isStart) {
return -1;
} else {
return 1;
}
}
});
PriorityQueue<Integer> pq = new PriorityQueue<>(
Collections.reverseOrder());

for (int i = 0; i < edges.size(); i++) {
Edge edge = edges.get(i);
if (edge.isStart) {
pq.offer(edge.y);
if (edge.y == pq.peek()) {
if(result.isEmpty()){
// first edge
}else if (edge.y!=result.get(result.size()-1)[1]){
// a left edge becomes key point
}
}
} else {
pq.remove(edge.y);
if (pq.isEmpty()) {
// last one, check if we have a phanton key point- whose line has length zero
while(result.peekLast()[0]==edge.x){
result.pollLast();
}
int[] point = new int[2];
point[0] = edge.x;
point[1] = 0;
} else if (pq.peek() != result.peekLast()[1] ) {
// a right edge becomes key point
int[] point = new int[2];
point[0] = edge.x;
point[1] = pq.peek();
}
}

}
return result;
}

private int[] toArray(Edge edge, boolean isTop) {
int[] coordinate = new int[2];
coordinate[0] = edge.x;
coordinate[1] = isTop ? edge.y : 0;
return coordinate;
}

private List<Edge> parseEdges(int[][] buildings) {
List<Edge> edges = new ArrayList<>();
for (int[] b : buildings) {

}
return edges;
}
}``````

• I had the similar idea as yours. My idea is using a max heap to get current height of skyline. So we can put a height into heap when meet a starting point or remove a height out when meet a end point. The tricky I used for multiple buildings starts at the same point, I let the sorting put the higher building at beginning and for end point, I let the lower building at beginning:

``````public class Solution
{
private static class KeyPoint
{
final int p;
final Integer h;
KeyPoint(final int p, final Integer h)
{
this.p = p;
this.h = h;
}
}

public List<int[]> getSkyline(int[][] buildings)
{
if (null == buildings || buildings.length <= 0)
{
return Collections.emptyList();
}
final KeyPoint[] starts = new KeyPoint[buildings.length];
final KeyPoint[] ends = new KeyPoint[starts.length];

for (int i = 0; i < buildings.length; ++i)
{
starts[i] = new KeyPoint(buildings[i][0], Integer.valueOf(buildings[i][2]));
ends[i] = new KeyPoint(buildings[i][1], starts[i].h);
}

Arrays.sort(starts, new Comparator<KeyPoint>(){
@Override
public int compare(final KeyPoint p1, final KeyPoint p2)
{
return p1.p == p2.p ? Integer.compare(p2.h, p1.h) : Integer.compare(p1.p, p2.p);
}
});
Arrays.sort(ends, new Comparator<KeyPoint>(){
@Override
public int compare(final KeyPoint p1, final KeyPoint p2)
{
return p1.p == p2.p ? Integer.compare(p1.h, p2.h) : Integer.compare(p1.p, p2.p);
}
});

final PriorityQueue<Integer> q = new PriorityQueue<>(ends.length, new Comparator<Integer>(){
@Override
public int compare(final Integer i1, final Integer i2)
{
return Integer.compare(i2, i1);
}
});
final List<int[]> rs = new ArrayList<int[]>();
int h = 0;
for (int is = 0, ie = 0; ie < ends.length; )
{
while (is < starts.length && starts[is].p < ends[ie].p)
{
q.offer(starts[is].h);

if (q.peek() != h)
{
h = q.peek();
final int[] r = {starts[is].p, h};
}
++is;
}

if (is < starts.length && starts[is].p == ends[ie].p)
{
while (starts[is].p == ends[ie].p)
{
q.remove(ends[ie++].h);
}
}
else
{
q.remove(ends[ie].h);
final int newH = q.isEmpty() ? 0 : q.peek();

if (h != newH)
{
h = newH;
final int[] r = {ends[ie].p, h};