8000 New Problem "The Skyline Problem" · xuyebing/chenhao-leetcode@9c00550 · GitHub
[go: up one dir, main page]
Skip to content

Commit 9c00550

Browse files
haoelhaoel
committed
New Problem "The Skyline Problem"
1 parent 1d6efde commit 9c00550

File tree

2 files changed

+141
-0
lines changed

2 files changed

+141
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -7,6 +7,7 @@ LeetCode
77

88
| # | Title | Solution | Difficulty |
99
|---| ----- | -------- | ---------- |
10+
|202|[The Skyline Problem](https://leetcode.com/problems/the-skyline-problem/)| [C++](./algorithms/theSkylineProblem/TheSkylineProblem.cpp)|Hard|
1011
|201|[Contains Duplicate](https://leetcode.com/problems/contains-duplicate/)| [C++](./algorithms/containsDuplicate/ContainsDuplicate.cpp)|Easy|
1112
|200|[Combination Sum III](https://leetcode.com/problems/combination-sum-iii/)| [C++](./algorithms/combinationSum/combinationSum.III.cpp)|Medium|
1213
|199|[Kth Largest Element in an Array](https://leetcode.com/problems/kth-largest-element-in-an-array/)| [C++](./algorithms/kthLargestElementInAnArray/KthLargestElementInAnArray.cpp)|Medium|

‎algorithms/theSkylineProblem/TheSkylineProblem.cpp

Lines changed: 140 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,140 @@
1+
// Source : https://leetcode.com/problems/the-skyline-problem/
2+
// Author : Hao Chen
3+
// Date : 2015-06-11
4+
5+
/**********************************************************************************
6+
*
7+
* A city's skyline is the outer contour of the silhouette formed by all the buildings
8+
* in that city when viewed from a distance. Now suppose you are given the locations and
9+
* height of all the buildings as shown on a cityscape photo (Figure A), write a program
10+
* to output the skyline formed by these buildings collectively (Figure B).
11+
*
12+
* ^ ^
13+
* | |
14+
* | |
15+
* | +-----+ | O-----+
16+
* | | | | | |
17+
* | | | | | |
18+
* | | +--+------+ | | O------+
19+
* | | | | | | |
20+
* | +-+--+----+ | +------+ | O-+ | O------+
21+
* | | | | | | | | | | |
22+
* | | | | | +-+--+ | | | | O--+  
23+
* | | | | | | | | | | | |
24+
* | | | | | | | | | | | |
25+
* | | | | | | | | | | | |
26+
* | | | | | | | | | | | |
27+
* +--+---------+----+---+----+----+---> +--+--------------O---+---------O--->
28+
*
29+
* https://leetcode.com/static/images/problemset/skyline1.jpg
30+
* https://leetcode.com/static/images/problemset/skyline2.jpg
31+
*
32+
* The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi],
33+
* where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively,
34+
* and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 , and Ri - Li > 0.
35+
* You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.
36+
*
37+
* For instance, the dimensions of all buildings in Figure A are recorded as:
38+
* [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .
39+
*
40+
* The output is a list of "key points" (red dots in Figure B) in the format of
41+
* [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline.
42+
* A key point is the left endpoint of a horizontal line segment.
43+
*
44+
* Note that the last key point, where the rightmost building ends, is merely used to mark
45+
* the termination of the skyline, and always has zero height. Also, the ground in between
46+
* any two adjacent buildings should be considered part of the skyline contour.
47+
*
48+
* For instance, the skyline in Figure B should be represented as:
49+
* [ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].
50+
*
51+
* Notes:
52+
*
53+
* - The number of buildings in any input list is guaranteed to be in the range [0, 10000].
54+
* - The input list is already sorted in ascending order by the left x position Li.
55+
* - The output list must be sorted by the x position.
56+
* - There must be no consecutive horizontal lines of equal height in the output skyline.
57+
* For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable;
58+
* the three lines of height 5 should be merged into one in the final output as such:
59+
* [...[2 3], [4 5], [12 7], ...]
60+
*
61+
* Credits: Special thanks to @stellari for adding this problem,
62+
* creating these two awesome images and all test cases.
63+
*
64+
**********************************************************************************/
65+
66+
67+
68+
/*
69+
* Sweep line with max-heap
70+
* ------------------------
71+
* Notice that "key points" are either the left or right edges of the buildings.
72+
*
73+
* Therefore, we first obtain both the edges of all the N buildings, and store the 2N edges in a sorted array.
74+
* Maintain a max-heap of building heights while scanning through the edge array:
75+
* 1) If the current edge is a left edge, then add the height of its associated building to the max-heap;
76+
* 2) If the edge is a right one, remove the associated height from the heap.
77+
*
78+
* Then we take the top value of the heap (yi) as the maximum height at the current edge position (xi).
79+
* Now (xi, yi) is a potential key point.
80+
*
81+
* If yi is the same as the height of the last key point in the result list, it means that this key point
82+
* is not a REAL key point, but rather a horizontal continuation of the last point, so it should be discarded;
83+
*
84+
* otherwise, we add (xi,yi) to the result list because it is a real key point.
85+
*
86+
* Repeat this process until all the edges are checked.
87+
*
88+
* It takes O(NlogN) time to sort the edge array. For each of the 2N edges,
89+
* it takes O(1) time to query the maximum height but O(logN) time to add
90+
* or remove elements. Overall, this solution takes O(NlogN) time.
91+
*/
92+
class Solution {
93+
public:
94+
95+
vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
96+
vector< pair<int, int> > edges;
97+
98+
//put all of edge into a vector
99+
//set left edge as negtive, right edge as positive
100+
//so, when we sort the edges,
101+
// 1) for same left point, the height would be descending order
102+
// 2) for same right point, the height would be ascending order
103+
int left, right, height;
104+
for(int i=0; i<buildings.size(); i++) {
105+
left = buildings[i][0];
106+
right = buildings[i][1];
107+
height = buildings[i][2];
108+
edges.push_back(make_pair(left, -height));
109+
edges.push_back(make_pair(right, height));
110+
}
111+
sort(edges.begin(), edges.end());
112+
113+
// 1) if we meet a left edge, then we add its height into a `set`.
114+
// the `set` whould sort the height automatically.
115+
// 2) if we meet a right edge, then we remove its height from the `set`
116+
//
117+
// So, we could get the current highest height from the `set`, if the
118+
// current height is different with preivous height, then we need add
119+
// it into the result.
120+
vector< pair<int, int> > result;
121+
multiset<int> m;
122+
m.insert(0);
123+
int pre = 0, cur = 0;
124+
for (int i=0; i<edges.size(); i++){
125+
pair<int,int> &e = edges[i];
126+
if (e.second < 0) {
127+
m.insert(-e.second);
128+
}else{
129+
m.erase(m.find(e.second));
130+
}
131+
cur = *m.rbegin();
132+
if (cur != pre) {
133+
result.push_back(make_pair(e.first, cur));
134+
pre = cur;
135+
}
136+
}
137+
return result;
138+
139+
}
140+
};

0 commit comments

Comments
 (0)
0