218. The Skyline Problem

/**

218. The Skyline Problem

A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Given the locations and heights of all the buildings, return the skyline formed by these buildings collectively.

The geometric information of each building is given in the array buildings where buildings[i] = [lefti, righti, heighti]:

  • lefti is the x coordinate of the left edge of the ith building.
  • righti is the x coordinate of the right edge of the ith building.
  • heighti is the height of the ith building.

You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

The skyline should be represented as a list of “key points” sorted by their x-coordinate in the form [[x1,y1],[x2,y2],…]. Each key point is the left endpoint of some horizontal segment in the skyline except the last point in the list, which always has a y-coordinate 0 and is used to mark the skyline’s termination where the rightmost building ends. Any ground between the leftmost and rightmost buildings should be part of the skyline’s contour.

Note: There must be no consecutive horizontal lines of equal height in the output skyline. For instance, […,[2 3],[4 5],[7 5],[11 5],[12 7],…] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: […,[2 3],[4 5],[12 7],…]

Example 1:

Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]

Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]

Explanation:

Figure A shows the buildings of the input.

Figure B shows the skyline formed by those buildings. The red points in figure B represent the key points in the output list.

Example 2:

Input: buildings = [[0,2,3],[2,5,3]]

Output: [[0,3],[5,0]]

Constraints:

  • 1 <= buildings.length <= 104
  • 0 <= lefti < righti <= 231 – 1
  • 1 <= heighti <= 231 – 1
  • buildings is sorted by lefti in non-decreasing order.

*/

See solution to the problem on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/frequent/hard/Skyline.java

This is a common interview question. Conceptually it is simple to solve but has complicated edge cases related to ordering the heights. 

The problem is asking to print out the sky line. Sky line at any X coordinate will be determined by the max Y coordinate at that point and changes to the sky line are recorded when max height at a given X changes. 

The problem can be solved with a combination of priority queue that stores the maximum current height and a means of iterating through heights in increasing X order with following constraints :

  • If two buildings are starting at same x axis
  • Pick the higher height first (this is because we want to give priority to the higher height).
  • If a building of same height starts and ends at the same point
    • Give priority to the building that is starting as the skyline will in fact not change even though a building is ending.
  • If two buildings end at the same X axis
    • Give priority to the building with smaller height (this is so the order of skyline is correct – otherwise, if we remove the higher height first we will record the smaller height as the next sky line coordinate whereas if no more buildings exist the skyline should have a Y of 0). 

Algorithm:

  1. Sort the heights based on the above logic.
  2. Add to the priority queue a sentinel height of 0 , so that we always have access to a minimum 0 height.
  3. Iterate through the sorted heights while adding them to the priority queue when a new building starts and removing that height from priority queue when a building ends. 
  4. Keep record of the current skyline height, when current max height in priority queue is different from that of the previously recorded max height add that coordinate as the new skyline coordinate. 

Here is the comparator used to sort the heights based on the above logic:

public int compareTo(Object o) {
    Height oH = (Height) o;
    if (xCoordinate == oH.xCoordinate) {
        if (isStart && oH.isStart) {
            //add in height decreasing order for start items -- i,e add higher height first
            return Integer.compare(oH.height, this.height);
        } else if (!isStart && !oH.isStart) {
            //add in height increasing order for end items -- i,e add lower height first
            return Integer.compare(this.height, oH.height);
        } else {
            if (this.isStart) return -1; // have start come before end for same x
            else return 1;
        }
    } else {
        if (xCoordinate > oH.xCoordinate) return 1;
        else return -1;
    }
}

Once heights are sorted, iterate through them while recording the X,Y coordinate whenever max height changes as below. Note that we are using a treemap as the basis of a priority queue. This is because we need to store the number of buildings with a given height where we increment the count or decrement it when the number of buildings changes. 

public List<List<Integer>> getSkyline(int[][] buildings) {
    List<Height> heights = new ArrayList<>();
    for (int[] building : buildings) {
        Height h = new Height();
        h.xCoordinate = building[0];
        h.height = building[2];
        h.isStart = true;

        Height h2 = new Height();
        h2.xCoordinate = building[1];
        h2.height = building[2];
        h2.isStart = false;
        heights.add(h);
        heights.add(h2);
    }

    Collections.sort(heights);
    List<List<Integer>> output = new ArrayList<>();
    //tree is used instead of a priority queue because it supports log N inserts and deletes
    TreeMap<Integer, Integer> priorityQueue = new TreeMap<>();
    //this sentinel is important. when an item is deleted from the queue the queue is basically empty
    //but we want the queue to indicate height as 0 and hence this value
    priorityQueue.put(0, 1);
    int prevH = 0;
    for (Height h : heights) {
        boolean isStart = h.isStart;
        //map.merge simplifies code.
        if (isStart) {
            //if height already exists add 1 to it, otherwise add a new height of 1
            priorityQueue.merge(h.height, 1, Integer::sum);
        } else {
            //decrement height by 1, if the count reaches 0, remove it.
            priorityQueue.merge(h.height, 1, (prev, one) -> {
                int n = prev - one;
                if (n == 0) return null;
                else return n;
            });
        }
        //get height item in queue
        int currH = priorityQueue.lastKey();
        if (currH != prevH) {
            //only output when last height is changing
            List<Integer> arr = new ArrayList<>();
            arr.add(h.xCoordinate);
            arr.add(currH);
            output.add(arr);
            prevH = currH;
        }
    }
    return output;
}