TreeMap solution, guaranteed to O(n logN)


  • 0
    X

    I scan all the points, while keeping a map of all existing heights:

    class heightComparator implements Comparator<int[]> {
    
    	@Override
    	public int compare(int[] o1, int[] o2) {
    		// if both arrays are at the same position, put the one with greater height first
    		if (o1[0] != o2[0])
    			return o1[0] - o2[0];
    		else
    			return o2[1] - o1[1];
    	}
    	
    }
    public class Solution {
    	public List<int[]> getSkyline(int[][] buildings) {
    		List<int[]> res = new ArrayList<>();
    		if (buildings == null || buildings.length == 0)
    			return res;
    		int n = buildings.length;
    		int[][] heights = new int[2 * n][2];
    		for (int i =  0; i < n; ++i) {
    			//e.g. for  [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ], store [2  10], [9, -10]
    			heights[2 * i][0] = buildings[i][0];
    			heights[2 * i][1] = buildings[i][2];
    			
    			heights[2 * i + 1][0] = buildings[i][1];
    			heights[2 * i + 1][1] = -buildings[i][2];
    		}
    		
    		Arrays.sort(heights, new heightComparator());
    		
    		// Then scan from left to right
    		TreeMap<Integer, Integer> cnt = new TreeMap<>();
    
    		for (int i = 0; i < 2 * n; ++i) {
    			int this_pos = heights[i][0];
    			int this_height = heights[i][1];
    			if (this_height > 0) {
    				cnt.put(this_height, cnt.getOrDefault(this_height, 0) + 1);
    			} else {
    				int this_cnt = cnt.get(-this_height);
    				if (this_cnt > 1) {
    					cnt.put(-this_height, this_cnt - 1);
    				} else
    					cnt.remove(-this_height);
    			}
    			
    			if (i < 2 * n - 1 && heights[i][0] == heights[i + 1][0])
    				continue;
    			
    			// try to update with new height
    			int cur_height = (cnt.isEmpty()) ? 0 : cnt.lastKey();
    			if (res.size() == 0 || cur_height != res.get(res.size() - 1)[1])
    				res.add(new int[] {this_pos, cur_height});
    		}
    		return res;
    	}
    }
    

Log in to reply
 

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