Java AC solution with comments


  • 0
    F

    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) {
    				    // if everything is the same, then start with left edge
    					return -1;
    				} else {
    					return 1;
    				}
    			}
    		});
    		LinkedList<int[]> result = new LinkedList<>();
    		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
    						result.add(toArray(edge, true));
    					}else if (edge.y!=result.get(result.size()-1)[1]){
    						// a left edge becomes key point
    						result.add(toArray(edge, true));
    					}
    				}
    			} 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;
    					result.add(point);
    				} 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();
    					result.add(point);
    				}
    			}
    			
    
    		}
    		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) {
    			edges.add(new Edge(b[0], b[2], true));
    			edges.add(new Edge(b[1], b[2], false));
    			
    		}
    		return edges;
    	}
    }

  • 1
    L

    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};
                        rs.add(r);
                    }
                    ++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};
                        rs.add(r);
                    }
                    
                    ++ie;
                }
            }
            
            return rs;
        }
    }

Log in to reply
 

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