The Skyline Problem

LeetCode Q 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. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

Solution

• When you reach a start point, the height of current building immediately takes effect which means it could possibly affect the contour or shadow others when mixed with other following buildings;
• When you reach a end point, the height of current building will stop its influences;

Code:

public List<int[]> getSkyline(int[][] buildings) {
	List<int[]> res = new ArrayList<>();
	List<int[]> heights = new ArrayList<>();

	// we store the left and right heights seperately!
	// in the heights, the int[] has size 2. 
	// int[0]: l / r position; int[1]: height
	for (int[] building: buildings) {
		heights.add(new int[] {building[0], -building[2]}); // neg value indicates it's left point;
		heights.add(new int[] {building[1], building[2]}); // pos value indicates it's right point;
	}
	
	// sort the list in ascending order
	// for example [2, 9, 10], [2, 9, 15], we want [2, -15], [2, -10], [9, 10], [9, 15];
	Collections.sort(heights, (a, b) -> {
		if (a[0] != b[0]) return a[0] - b[0];
		return a[1] - b[1];
	});	

	// pq is used to store the height value, we want the larger one comes first.
	Queue<Integer> pq = new PriorityQueue<>((a,b) -> (b - a));

	int prev = 0; pq.offer(0);
	for (int[] arr: heights) {
		if (arr[1] < 0) // indicates a left point, we offer the height value into the queue
			pq.offer(-arr[1]); // since we want it to impact others
		if (arr[1] > 0) // indicates a right point, remove the height value from the queue
			pq.remove(arr[1]); // since we want that height value to stop its influence
		int curr = pq.peek();
		if (curr != prev) {
			res.add(new int[] {arr[0], curr});
			prev = curr;
		}
	}

	return res;
}