The Skyline Problem
This problem is a little hard. Given a series of buildings, we reserve a queue where in the queue the buildings is sorted by their right sides' position and their height is descending all the way. Note that the won't be a building in the queue contains right top point of another building in the queue.
We we are going to add next building, first from the head of queue we poll all buildings whose right side is on the left of left side of current building as these buildings won't affect skyline after current building's left side. Then we removes all buildings in the queue whose top right point is contained by current building. At last we insert current building to a proper position in the queue.
To build the result, we add upstair points when we first meet a buildings if it is higher than any buildings in the queue. Noted that many buildings may have the same left side position, so when adding upstair points, we first check last points and make sure the buildings with same left side position only contribute one highest upstair point in the result. We add downstair points when poll bulidings whose right side is at the left of current building as well as in the end of program to empty queue.
There are two ways to implement this algorithm. The first is using LinkedList
and insertion method
when adding items into the queue. The other method is using a PriorityQueue
and let the PriorityQueue
to sort buildings for us.
The LinkedList
solution:
import java.util.*;
public class TheSkylineProblem {
public List<int[]> getSkyline(int[][] buildings) {
ArrayList<int[]> result = new ArrayList<int[]>();
if (buildings.length == 0 || buildings[0].length == 0) return result;
LinkedList<Integer> queue = new LinkedList<Integer>();
for (int i = 0; i < buildings.length; i++) {
int l = buildings[i][0], r = buildings[i][1], h = buildings[i][2];
while (!queue.isEmpty() && buildings[queue.getFirst()][1] < l) {
int right = buildings[queue.pollFirst()][1];
int height = queue.isEmpty() ? 0 : buildings[queue.getFirst()][2];
int[] newpoint = {right, height};
result.add(newpoint);
}
if (queue.isEmpty() || buildings[queue.getFirst()][2] < h) {
if (!result.isEmpty() && result.get(result.size() - 1)[0] == l) {
int[] last = result.get(result.size() - 1);
last[1] = Math.max(last[1], h);
} else {
int[] newpoint = {l, h};
result.add(newpoint);
}
}
ListIterator<Integer> iter = queue.listIterator();
while (iter.hasNext()) {
int index = iter.next();
if (buildings[index][1] <= r && buildings[index][2] <= h) {
iter.remove();
}
}
if (queue.isEmpty()) queue.addLast(i);
else {
iter = queue.listIterator();
while (iter.hasNext()) {
int index = iter.next();
if (buildings[index][1] >= r && buildings[index][2] >= h) break;
if (buildings[index][2] < h) {
iter.set(i);
iter.add(index);
break;
}
if (!iter.hasNext()) {
iter.add(i);
break;
}
}
}
}
while (!queue.isEmpty()) {
int right = buildings[queue.pollFirst()][1];
int height = queue.isEmpty() ? 0 : buildings[queue.getFirst()][2];
int[] newpoint = {right, height};
result.add(newpoint);
}
return result;
}
}
The PriorityQueue
solution:
import java.util.*;
// Solve the skyline problem with priority queue
public class TheSkylineProblemII {
public List<int[]> getSkyline(int[][] buildings) {
ArrayList<int[]> result = new ArrayList<int[]>();
if (buildings.length == 0 || buildings[0].length == 0) return result;
final int[][] innerBuildings = buildings;
PriorityQueue<Integer> queue = new PriorityQueue<Integer>(
buildings.length,
new Comparator<Integer>() {
public int compare(Integer a, Integer b) {
return innerBuildings[a][1] - innerBuildings[b][1];
}
});
for (int i = 0; i < buildings.length; i++) {
int l = buildings[i][0], r = buildings[i][1], h = buildings[i][2];
while (!queue.isEmpty() && buildings[queue.peek()][1] < l) {
int right = buildings[queue.poll()][1];
int height = queue.isEmpty() ? 0 : buildings[queue.peek()][2];
int[] newpoint = {right, height};
result.add(newpoint);
}
if (queue.isEmpty() || buildings[queue.peek()][2] < h) {
if (!result.isEmpty() && result.get(result.size() - 1)[0] == l) {
int[] last = result.get(result.size() - 1);
last[1] = Math.max(last[1], h);
} else {
int[] newpoint = {l, h};
result.add(newpoint);
}
}
Iterator<Integer> iter = queue.iterator();
boolean flag = true;
while (iter.hasNext()) {
int index = iter.next();
if (buildings[index][1] <= r && buildings[index][2] <= h) {
iter.remove();
continue;
}
if (buildings[index][1] >= r && buildings[index][2] >= h) {
flag = false;
}
}
if (flag) queue.offer(i);
}
while (!queue.isEmpty()) {
int right = buildings[queue.poll()][1];
int height = queue.isEmpty() ? 0 : buildings[queue.peek()][2];
int[] newpoint = {right, height};
result.add(newpoint);
}
return result;
}
}