LC 218


TreeMap.

public List<int[]> getSkyline(int[][] buildings) {
    List<int[]> res = new ArrayList<>();
    if(buildings.length == 0) {
        return res;
    }
    PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> (a[0] == b[0]) ? b[1] - a[1]: a[0] - b[0]);
    for(int[] building: buildings) {
        queue.offer(new int[]{building[0], building[2]});
        queue.offer(new int[]{building[1], -building[2]});
    }

    // TreeMap => RBT. So we can do both: get max/min value and insert/del elements in O(logN).
    TreeMap<Integer, Integer> heightTree = new TreeMap<>(Collections.reverseOrder());
    heightTree.put(0, 0);
    while(!queue.isEmpty()) {
        int[] point = queue.poll();
        // New building occured.
        if(point[1] > 0) {
            // The new building is the heightest one.
            if(point[1] > heightTree.firstKey()) {
                res.add(new int[] {point[0], point[1]});
            }
            int count = heightTree.getOrDefault(point[1], 0);
            heightTree.put(point[1], count + 1);
        }
        // A building reaches its end.
        else {
            int count = heightTree.get(-point[1]);
            // The new building is the heightest one, and the only one.
            if(count == 1) {
                int firstKey = heightTree.firstKey();
                heightTree.remove(-point[1]);
                if(firstKey == -point[1]) {
                    res.add(new int[] {point[0], heightTree.firstKey()});
                }
            } else {
                heightTree.put(-point[1], count - 1);
            }
        }
    }
    return res;
}

results matching ""

    No results matching ""