Skyline Problem

https://leetcode.com/problems/the-skyline-problem/

This video is super clear and helpful: https://www.youtube.com/watch?v=GSBLe8cKu0s

  •  Algorithm:
    • First observation: all the points in the final result come from the four angles that each building has
    • Scan through the horizontal lines
    • Use a PriorityQueue to hold each building, and make the PriorityQueue to sort on the height of the buildings
    • whenever we encounter the start of a building, we push it into the PriorityQueue, whenever we finished scanning that building, we remove it from the PriorityQueue
    • Also, in the scan process, we’ll keep updating the maxHeight in the PriorityQueue if we find a new maxHeight which means the building will be overshadowed by the new higher one

 

  • Three edge cases (see the graph illustration in the above video at 12’18”):
    1. when two buildings have the same start point, the one with higher height shows up in the final result
    2. when two buildings have the same end point, the one with higher height shows up in the final result
    3. when the start point of one building is is also the end point of another building, the one with higher height shows up in the final result

 

  •  We use TreeMap over a normal PriorityQueue:
    • For the sake of efficiency (better time complexity), we’ll use TreeMap which supports O(logn) for remove() operation, this is the reason we choose TreeMap over a normal PriorityQueue in Java (PriorityQueue supports add() and getMaxVal() in both O(logn) time, however, for remove(), it does NOT.)
    • But TreeMap in Java supports all the three operations in O(logn) time.

 

public List<int[]> getSkyline(int[][] buildings) {

//construct a new array and its length should be buildings.length*2, since each building will have two BuildingPoint
BuldingPoint[] bps = new BuldingPoint[buildings.length*2];
int index = 0;
for(int[] building : buildings){
BuldingPoint startPoint = new BuldingPoint(building[0], true, building[2]);
BuldingPoint endPoint = new BuldingPoint(building[1], false, building[2]);
bps[index] = startPoint;
bps[index+1] = endPoint;
index += 2;
}
Arrays.sort(bps);

List<int[]> res = new ArrayList<int[]>();
TreeMap<Integer, Integer> map = new TreeMap();//we use height as the key, number of times this height appears as the value
map.put(0, 1);//this line is very helpful in initializing the map, although it doesn't mean anything: or you could say it means height zero appears once
int prevMaxHeight = 0;
for(BuldingPoint bp : bps){
//if it's a start point, then we add the height into the map, if it's already there, we just increment its count
if(bp.isStart){
if(map.containsKey(bp.height)) map.put(bp.height, (map.get(bp.height)+1));
else map.put(bp.height, 1);
}

//if it's an end point, then we remove its heigh from the map or decrement it count by 1 if it's greater than 1
else if(!bp.isStart){
if(map.containsKey(bp.height) && map.get(bp.height) > 1) map.put(bp.height, (map.get(bp.height)-1));
else map.remove(bp.height);
}

int currentMaxHeight = map.lastKey();
//this comment is another key for this algorithm: if maxHeight changes, that means this buildingPoint is a critical one, so we need to add it to final result
if(currentMaxHeight != prevMaxHeight){
res.add(new int[]{bp.x, currentMaxHeight});
prevMaxHeight = currentMaxHeight;
}
}

return res;

}

class BuldingPoint implements Comparable<BuldingPoint>{
int x;
boolean isStart;
int height;

public BuldingPoint(int x, boolean isStart, int height){
this.x = x;
this.isStart = isStart;
this.height = height;
}

@Override
public int compareTo(BuldingPoint o) {
/**Comparision logic:
* if x are different, then use x
* if x are the same, then:
* if both are start points, then the one with higher height wins
* if both are end points, then the one with lower height wins
* if one is start point, the other is end point, then the start point wins
* */
if(this.x != o.x){
return this.x - o.x;
} else {
return (this.isStart ? -this.height : this.height) - (o.isStart ? -o.height : o.height);
}
}
}

Advertisements