My 900+ms Java solution, Priority Queue


  • 0
    W

    Use priority queue to store the buildings.

    900+ ms :(

    public class Solution {
    class building{
    int left;
    int right;
    int height;

    	building(int l, int r, int h){
    		left = l;
    		right = r;
    		height = h;
    	}
    }
    
    public static List<int[]> getSkyline(int[][] buildings) {
    	
    	List<int[]> res = new ArrayList<int[]>();
    	
    	if(buildings.length == 0){
    		return res;
    	}
    	
        Comparator<building> Order =  new Comparator<building>(){  
            public int compare(building b1, building b2) {  
                // TODO Auto-generated method stub  
            	
            	if(b1.left != b2.left){	
            		return b1.left - b2.left;
            	}
            	else{
            		return b2.height - b1.height;
            	}    
            }               
        }; 
    	
    	PriorityQueue<building> list = new PriorityQueue<building>(buildings.length, Order);
    	
    	int end = buildings[0][1];
    	
    	building t = null;
    	
    	for(int i=0; i<buildings.length; i++){		
    		if(end < buildings[i][0]){
    			t = new building(end,buildings[i][0],0);
    			list.add(t);
    		}		
    		end = Math.max(end, buildings[i][1]);		
    		t = new building(buildings[i][0],buildings[i][1],buildings[i][2]);
    		list.add(t);
    	}
    	
    	building cur;
    	building tmp;
    	
    	int lastheight = -1;
    	int newpoint= -1;
    	
    	while(!list.isEmpty()){		
    		newpoint= -1;
    		cur = list.poll();
    		
    		if(cur.height != lastheight){
    			res.add(new int[]{cur.left,cur.height});
    		}
    		lastheight = cur.height;
    		
    		int count = list.size();
    		
    		for(int i=0; i<count; i++){
    			tmp = list.poll();
    			
    			if(tmp.left >= cur.right){	
    				list.add(tmp);
    				break;
    			}else if (tmp.right <= cur.right){	
    				if(tmp.height <= cur.height){
    					continue;
    				}
    				else{
    					list.add(tmp);
    					
    					newpoint= Math.max(newpoint, tmp.right);	
    				}
    			}else{	
    				if(tmp.height <= cur.height){
    					tmp.left = cur.right;
    					list.add(tmp);
    				}
    				else{
    					list.add(tmp);
    				}
    			}	
    		}
    		if(lastpoint != -1 && lastpoint < cur.right){
    			list.add(new building(lastpoint,cur.right,cur.height));
    			count ++;
    		}	
    	}	
    	res.add(new int[]{end,0});	
    	return res;
    }
    

    }


Log in to reply
 

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