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).
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], ...]
Idea:
Sweep line
Time Complexity:
O(nlogn)
Space Complexity:
O(n)
Solution1: Heap
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 |
class Solution { public: vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) { // events, x, h, id, type (1=entering, -1=leaving) vector<Event> events; int id = 0; for (const auto& b : buildings) { events.push_back(Event{id, b[0], b[2], 1}); events.push_back(Event{id, b[1], b[2], -1}); ++id; } // Sort events by x sort(events.begin(), events.end()); // Init the heap MaxHeap heap(buildings.size()); vector<pair<int, int>> ans; // Process all the events for (const auto& event: events) { int x = event.x; int h = event.h; int id = event.id; int type = event.type; if (type == 1) { if (h > heap.Max()) ans.emplace_back(x, h); heap.Add(h, id); } else { heap.Remove(id); if (h > heap.Max()) ans.emplace_back(x, heap.Max()); } } return ans; } private: struct Event { int id; int x; int h; int type; // sort by x+, type-, h, bool operator<(const Event& e) const { if (x == e.x) // Entering event h from large to small // Leaving event h from small to large return type * h > e.type * e.h; return x < e.x; } }; class MaxHeap { public: MaxHeap(int max_items): idx_(max_items, -1), vals_(max_items), size_(0) {} // Add an item into the heap. O(log(n)) void Add(int key, int id) { idx_[id] = size_; vals_[size_] = {key, id}; ++size_; HeapifyUp(idx_[id]); } // Remove an item. O(log(n)) void Remove(int id) { int idx_to_evict = idx_[id]; // swap with the last element SwapNode(idx_to_evict, size_ - 1); --size_; HeapifyDown(idx_to_evict); HeapifyDown(idx_to_evict); } bool Empty() const { return size_ == 0; } // Return the max of heap int Max() const { return Empty() ? 0 : vals_.front().first; } private: void SwapNode(int i, int j) { if (i == j) return; std::swap(idx_[vals_[i].second], idx_[vals_[j].second]); std::swap(vals_[i], vals_[j]); } void HeapifyUp(int i) { while (i != 0) { int p = (i - 1) / 2; if (vals_[i].first <= vals_[p].first) return; SwapNode(i, p); i = p; } } // Make the heap valid again. O(log(n)) void HeapifyDown(int i) { while (true) { int c1 = i*2 + 1; int c2 = i*2 + 2; // No child if (c1 >= size_) return; // Get the index of the max child int c = (c2 < size_ && vals_[c2].first > vals_[c1].first ) ? c2 : c1; // If key[c] is greater than key[i], swap them and // continue to HeapifyDown(c) if (vals_[c].first <= vals_[i].first) return; SwapNode(c, i); i = c; } } // {key, id} vector<pair<int,int>> vals_; // Index of the i-th item in vals_ vector<int> idx_; int size_; }; }; |
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 |
// Author: Huahua // Running time: 91 ms (beats 79.1%) class Solution { private MaxHeap heap; public List<int[]> getSkyline(int[][] buildings) { int n = buildings.length; // {x, h, id} ArrayList<int[]> es = new ArrayList<int[]>(); for (int i = 0; i < n; ++i) { es.add(new int[]{ buildings[i][0], buildings[i][2], i}); es.add(new int[]{ buildings[i][1], -buildings[i][2], i}); } es.sort((e1, e2) -> { return e1[0] == e2[0] ? e2[1] - e1[1] : e1[0] - e2[0]; }); List<int[]> ans = new ArrayList<int[]>(); heap = new MaxHeap(n); for (int[] e : es) { int x = e[0]; int h = e[1]; int id = e[2]; Boolean entering = h > 0; h = Math.abs(h); if (entering) { if (h > heap.max()) ans.add(new int[]{x, h}); heap.add(h, id); } else { heap.remove(id); if (h > heap.max()) ans.add(new int[]{x, heap.max()}); } } return ans; } private class MaxHeap { // (key, id) private List<int[]> nodes; // idx[i] = index of building[i] in nodes private int[] idx; public MaxHeap(int size) { idx = new int[size]; nodes = new ArrayList<int[]>(); } public void add(int key, int id) { idx[id] = nodes.size(); nodes.add(new int[]{key, id}); heapifyUp(idx[id]); } public void remove(int id) { int idx_to_evict = idx[id]; swapNode(idx_to_evict, nodes.size() - 1); idx[id] = -1; nodes.remove(nodes.size() - 1); heapifyUp(idx_to_evict); heapifyDown(idx_to_evict); } public Boolean empty() { return nodes.isEmpty(); } public int max() { return empty() ? 0 : nodes.get(0)[0]; } private void heapifyUp(int i) { while (i != 0) { int p = (i - 1) / 2; if (nodes.get(i)[0] <= nodes.get(p)[0]) return; swapNode(i, p); i = p; } } private void swapNode(int i, int j) { int tmpIdx = idx[nodes.get(i)[1]]; idx[nodes.get(i)[1]] = idx[nodes.get(j)[1]]; idx[nodes.get(j)[1]] = tmpIdx; int[] tmpNode = nodes.get(i); nodes.set(i, nodes.get(j)); nodes.set(j, tmpNode); } private void heapifyDown(int i) { while (true) { int c1 = i*2 + 1; int c2 = i*2 + 2; if (c1 >= nodes.size()) return; int c = (c2 < nodes.size() && nodes.get(c2)[0] > nodes.get(c1)[0]) ? c2 : c1; if (nodes.get(c)[0] <= nodes.get(i)[0]) return; swapNode(c, i); i = c; } } } } |
Solution 2: Multiset
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
// Author: Huahua // Time Complexity: O(nlogn) // Space Complexity: O(n) // Running Time: 22 ms class Solution { public: vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) { typedef pair<int, int> Event; // events, x, h vector<Event> es; hs_.clear(); for (const auto& b : buildings) { es.emplace_back(b[0], b[2]); es.emplace_back(b[1], -b[2]); } // Sort events by x sort(es.begin(), es.end(), [](const Event& e1, const Event& e2){ if (e1.first == e2.first) return e1.second > e2.second; return e1.first < e2.first; }); vector<pair<int, int>> ans; // Process all the events for (const auto& e: es) { int x = e.first; bool entering = e.second > 0; int h = abs(e.second); if (entering) { if (h > this->maxHeight()) ans.emplace_back(x, h); hs_.insert(h); } else { hs_.erase(hs_.equal_range(h).first); if (h > this->maxHeight()) ans.emplace_back(x, this->maxHeight()); } } return ans; } private: int maxHeight() const { if (hs_.empty()) return 0; return *hs_.rbegin(); } multiset<int> hs_; }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment