The Skyline Problem
題意:畫出建築物的輪櫎
解題思路:
把每個building的上升邊與下降邊分別放入 list 並作排序,排放順序如下
- pos 較小的放前
- 若pos 一樣,如果同為上升邊,把較高的放前面
- 若是下降邊,把較矮的放前面
- 只有其中一邊是上升,把上升邊放前面
接著再不斷的根據邊的不同對 haep作操作
- 若為上升邊,則比較頂端高度輸出一個edge,再把自己加入
- 若為下降邊,則比較頂端高度
接著
public class Solution {
class Edge implements Comparator<Edge> {
int pos;
int height;
boolean isStart;
public Edge(int pos, int height, boolean isStart) {
this.pos = pos;
this.height = height;
this.isStart = isStart;
}
public Edge(){}
public int compare(Edge edgeOne, Edge edgeTwo) {
if (edgeOne.pos != edgeTwo.pos) {
return Integer.compare(edgeOne.pos, edgeTwo.pos);
} else if (edgeOne.isStart && edgeTwo.isStart) {
return Integer.compare(edgeTwo.height, edgeOne.height);
} else if (!edgeOne.isStart && !edgeTwo.isStart) {
return Integer.compare(edgeOne.height, edgeTwo.height); // 如果兩個都是下降,則較短的在前,較高的在後
} else {
return edgeOne.isStart ? -1 : 1;
}
}
}
public List<int[]> getSkyline(int[][] buildings) {
List<int[]> res = new ArrayList<int[]>();
if (buildings == null || buildings.length == 0 ||buildings[0].length == 0) {
return res;
}
List<Edge> edges = new ArrayList<Edge>();
for (int[] building : buildings) {
Edge startEdge = new Edge(building[0], building[2], true);
edges.add(startEdge);
Edge endEdge = new Edge(building[1], building[2], false);
edges.add(endEdge);
}
Collections.sort(edges, new Edge());
// min heap 把時間小放在前面
PriorityQueue<Integer> heap = new PriorityQueue<Integer>(1, Collections.reverseOrder());
for (Edge edge : edges) {
if (edge.isStart) {
if (heap.isEmpty() || edge.height > heap.peek()) {
res.add(new int[]{edge.pos, edge.height});
}
heap.add(edge.height);
} else {
heap.remove(edge.height);
if (heap.isEmpty() || edge.height > heap.peek()) {
res.add(heap.isEmpty() ? new int[]{edge.pos, 0} : new int[]{edge.pos, heap.peek()});
}
}
}
return res;
}
}