Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/218.html
218. The Skyline Problem
Level
Hard
Description
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).
The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi]
, where Li
and Ri
are the x coordinates of the left and right edge of the ith building, respectively, and Hi
is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX
, 0 < Hi ≤ INT_MAX
, and Ri - Li > 0
. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.
For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ]
.
The output is a list of “key points” (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ]
that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.
For instance, the skyline in Figure B should be represented as: [ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ]
.
Notes:
- The number of buildings in any input list is guaranteed to be in the range
[0, 10000]
. - The input list is already sorted in ascending order by the left x position
Li
. - The output list must be sorted by the x position.
- 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], ...]
Algorithm
Save the left
and right
nodes of each line segment to the new vector height, and sort them according to the x
coordinate value.
Then traverse to find the inflection point. When finding the inflection point, use a maximum heap to save the current roof height,
- When you encounter the left node, insert the height information in the heap,
- The height is deleted from the heap when the node on the right is encountered.
Use pre
and cur
to represent the previous height and the current height respectively,
- When
cur != pre
, it means that there is an inflection point. - Note that when deleting elements from the heap, I use priority_queue to implement it. Priority_queue does not provide delete operations, so another unordered_map is used to mark the elements to be deleted.
- When popping from the heap, first see if it has been marked,
- If it has been marked, pop until it is empty or all unmarked values are found. Don’t be careful when sorting externally.
-
If the
x
-coordinates of two nodes are the same, we have to consider other attributes of the nodes to order to avoid redundant answers. - And the rule of body is
- If they are all left nodes, sort them from largest to smallest according to the
y
coordinate, - If they are all right nodes, sort from small to large according to the
y
coordinate, one left node and one right node, let the left node be in the front
- If they are all left nodes, sort them from largest to smallest according to the
Code
Java
-
import java.util.*; public class The_Skyline_Problem { public static void main(String[] args) { The_Skyline_Problem out = new The_Skyline_Problem(); Solution_Heap s = out.new Solution_Heap(); // output: [ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ] s.getSkyline( new int[][]{ {2,9,10}, {3,7,15}, {5,12,12}, {15,20,10}, {19,24,8} } ) .stream().forEach(System.out::println); } class Solution_Heap { public List<List<Integer>> getSkyline(int[][] buildings) { List<List<Integer>> result = new ArrayList<>(); if (buildings == null || buildings.length == 0 || buildings[0].length == 0) { return result; } List<Edge> edges = new ArrayList<Edge>(); // add all left/right edges for (int[] each: buildings) { edges.add(new Edge(each[0], each[2], true)); edges.add(new Edge(each[1], each[2], false)); } // sort edges, NlogN Collections.sort(edges, (a, b) -> { if (a.x != b.x) { return Integer.compare(a.x, b.x); } if (a.isStart && b.isStart) { return Integer.compare(b.height, a.height); // higher edge at front } if (!a.isStart && !b.isStart) { return Integer.compare(a.height, b.height); // lower edge at front } return a.isStart ? -1 : 1; // lower edge at front }); // process edges, comparator is reverseOrder() PriorityQueue<Integer> heightHeap = new PriorityQueue<Integer>(Collections.reverseOrder()); for (Edge edge : edges) { if (edge.isStart) { if (heightHeap.isEmpty() || edge.height > heightHeap.peek()) { result.add(Arrays.asList( edge.x, edge.height )); } heightHeap.add(edge.height); } else { heightHeap.remove(edge.height); if (heightHeap.isEmpty()){ result.add( Arrays.asList(edge.x, 0) ); // last point } else if (edge.height > heightHeap.peek()){ // @note: intersect result.add( Arrays.asList(edge.x, heightHeap.peek()) ); } } } return result; } class Edge { int x; // x坐标 int height; boolean isStart; public Edge(int x, int height, boolean isStart) { this.x = x; this.height = height; this.isStart = isStart; } } } // merge sort example public class Solution_mergeSort { public List<int[]> getSkyline(int[][] buildings) { if(buildings == null || buildings.length == 0) { return new LinkedList<int[]>(); } return getSkyline(buildings, 0, buildings.length - 1); } // NlogN private LinkedList<int[]> getSkyline(int[][] buildings, int lo, int hi) { if (lo < hi) { int mid = lo + (hi - lo) / 2; return mergeSkylines(getSkyline(buildings, lo, mid), getSkyline(buildings, mid + 1, hi)); } else { // lo == hi, base case, add the final already-merged building to skyline LinkedList<int[]> skyline = new LinkedList<int[]>(); skyline.add(new int[]{buildings[lo][0], buildings[lo][2]}); // only care about [left-index, height] skyline.add(new int[]{buildings[lo][1], 0}); // right-index is just for last right edge return skyline; } } // merge two Skylines private LinkedList<int[]> mergeSkylines(LinkedList<int[]> skyline1, LinkedList<int[]> skyline2) { LinkedList<int[]> skyline = new LinkedList<int[]>(); int height1 = 0, height2 = 0; while(skyline1.size() > 0 && skyline2.size() > 0) { int index = 0, height = 0; // @note: always remove the smaller index first, so order is guaranteed if (skyline1.getFirst()[0] < skyline2.getFirst()[0]) { index = skyline1.getFirst()[0]; height1 = skyline1.getFirst()[1]; height = Math.max(height1, height2); skyline1.removeFirst(); } else if (skyline1.getFirst()[0] > skyline2.getFirst()[0]) { index = skyline2.getFirst()[0]; height2 = skyline2.getFirst()[1]; height = Math.max(height1, height2); skyline2.removeFirst(); } else { index = skyline1.getFirst()[0]; height1 = skyline1.getFirst()[1]; height2 = skyline2.getFirst()[1]; height = Math.max(height1, height2); skyline1.removeFirst(); skyline2.removeFirst(); } if (skyline.size() == 0 || height != skyline.getLast()[1]) { skyline.add(new int[]{index, height}); } } // final check skyline.addAll(skyline1); skyline.addAll(skyline2); return skyline; } } }
-
// OJ: https://leetcode.com/problems/the-skyline-problem/ // Time: O(NlogN) // Space: O(N) // Ref: https://discuss.leetcode.com/topic/14939/my-c-code-using-one-priority-queue-812-ms bool cmp(vector<int> &a, vector<int> &b) { return a[0] < b[0]; } class Solution { public: vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) { vector<pair<int, int>> ans; sort(buildings.begin(), buildings.end(), cmp); int i = 0, x = 0, y = 0, N = buildings.size(); priority_queue<pair<int, int>> live;// first: height, second: right while (i < N || !live.empty()) { if (i < N && (live.empty() || live.top().second >= buildings[i][0])) { x = buildings[i][0]; while (i < N && buildings[i][0] == x) { live.push(make_pair(buildings[i][2], buildings[i][1])); ++i; } } else { x = live.top().second; while (!live.empty() && live.top().second <= x) live.pop(); } y = live.empty() ? 0 : live.top().first; if (ans.empty() || ans.back().second != y) ans.push_back(make_pair(x, y)); } return ans; } };
-
''' >>> a = [] >>> a.append((3, 5)) >>> a.append((3, -5)) >>> a.append((2, -10)) >>> a.append((2, 10)) >>> a [(3, 5), (3, -5), (2, -10), (2, 10)] >>> a.sort() >>> a [(2, -10), (2, 10), (3, -5), (3, 5)] >>> from queue import PriorityQueue >>> pq = PriorityQueue() >>> >>> pq.put([1,2,3]) >>> pq.put([-10,20,30]) >>> pq.put([11,22,33]) >>> >>> pq <Queue.PriorityQueue instance at 0x10aec51b8> >>> pq.queue[0][0] -10 >>> pq.get() [-10, 20, 30] >>> pq.queue[0][0] 1 ''' from queue import PriorityQueue class Solution: def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]: skys, lines, pq = [], [], PriorityQueue() for build in buildings: lines.extend([build[0], build[1]]) lines.sort() city, n = 0, len(buildings) for line in lines: # 对于每一个边界线 lines[i],找出所有包含 lines[i] 的建筑物 while city < n and buildings[city][0] <= line: pq.put([-buildings[city][2], buildings[city][0], buildings[city][1]]) # 建筑物的高度构建优先队列(大根堆),这里会包括line自己的building city += 1 while not pq.empty() and pq.queue[0][2] <= line: # higher at heap top after negated pq.get() # i.e. pop() high = 0 # 建筑物的左边界小于等于 lines[i],右边界大于 lines[i],则这些建筑物中高度最高的建筑物的高度就是该线轮廓点的高度 if not pq.empty(): high = -pq.queue[0][0] if len(skys) > 0 and skys[-1][1] == high: # 绿色建筑的左边的line,就要跳过 continue skys.append([line, high]) return skys ############ import heapq class Solution(object): def getSkyline(self, buildings): """ :type buildings: List[List[int]] :rtype: List[List[int]] """ hs = [] heap = [] for b in buildings: hs.append((b[0], -b[2])) hs.append((b[1], b[2])) hs.sort() ans = [] pre = cur = None for h in hs: pos = h[0] height = h[1] if height < 0: heapq.heappush(heap, height) else: i = heap.index(-height) heap[i] = heap[-1] heap.pop() if i < len(heap): heapq._siftup(heap, i) heapq._siftdown(heap, 0, i) if heap: cur = heap[0] if cur != pre: ans.append((pos, -1 * cur)) pre = cur else: ans.append((pos, 0)) return ans