Let's make this one less mysterious. For 218. The Skyline Problem, the solution in this repository is mainly a heap / priority queue solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: heap / priority queue, binary search, two pointers, sliding window.
The notes already sitting in the source point us in the right direction:
- line sweep
- TLE
- 35 / 36 test cases passed.
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are operator, remove, update, query, add.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- Sorting is used to make local choices comparable, so the later scan does not have to rediscover order.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- The queue gives the solution a level-by-level or frontier-style traversal.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//line sweep
02//TLE
03//35 / 36 test cases passed.
04class Solution {
05public:
06 vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
07 int OPEN = 0, CLOSE = 1;
08 int n = buildings.size();
09 //vector of {x coord, open or close, height, building_id}
10 vector<vector<int>> events(n*2);
11
12 for(int i = 0; i < n; ++i){
13 events[i*2] = {buildings[i][0], OPEN, buildings[i][2], i};
14 events[i*2+1] = {buildings[i][1], CLOSE, buildings[i][2], i};
15 }
16
17 //actives: current opening events' event_id
18 vector<int> actives;
19 vector<vector<int>> ans;
20
21 //sort by x coord
22 sort(events.begin(), events.end());
23
24 // cout << "event" << endl;
25 // for(vector<int>& event : events){
26 // cout << "x: " << event[0] << ", " << (event[1] ? "CLOSE" : "OPEN") << ", height: " << event[2] << endl;
27 // }
28
29 int lastX = INT_MIN;
30 int lastMaxHeight = INT_MIN;
31
32 //vertical line sweep along x-axis
33 for(int eventId = 0; eventId < events.size(); ++eventId){
34 //extract the required infos
35 int x = events[eventId][0];
36 bool isClose = events[eventId][1];
37 int height = events[eventId][2];
38
39 // cout << "x: " << x << ", isClose: " << isClose << ", height: " << height << endl;
40
41 if(!isClose){
42 actives.push_back(eventId);
43 }else{
44 //find the corresponding OPEN event and remove it
45 for(int i = 0; i < actives.size(); ++i){
46 if(events[actives[i]][2] == height){
47 actives.erase(actives.begin()+i);
48 break;
49 }
50 }
51 }
52
53 // cout << "active: ";
54 // for(int& active : actives){
55 // cout << active << " ";
56 // }
57 // cout << endl;
58
59 //get the maximum height of active events
60 int maxHeight = 0;
61
62 //update actives
63 if(!actives.empty()){
64 for(int i = 0; i < actives.size(); ++i){
65 if(events[actives[i]][1] != CLOSE){
66 maxHeight = max(maxHeight, events[actives[i]][2]);
67 }
68 }
69 }
70
71 // cout << "maxHeight: " << maxHeight << endl;
72
73 //update ans only if x is leftmost or rightmost of actives
74 if(actives.empty()){
75 //the right boundary of connected buildings
76 ans.push_back({x, maxHeight});
77 }else if(!ans.empty() && x == ans.back()[0]){
78 //current event and last event has same x
79 //update its height
80 ans.back()[1] = maxHeight;
81 }else{
82 //there is a change in height
83 if(maxHeight != lastMaxHeight)
84 ans.push_back({x, maxHeight});
85 }
86
87 lastMaxHeight = maxHeight;
88 lastX = x;
89 }
90
91 return ans;
92 }
93};
94
95//line sweep + heap
96//https://briangordon.github.io/2014/08/the-skyline-problem.html
97//Runtime: 256 ms, faster than 5.24% of C++ online submissions for The Skyline Problem.
98//Memory Usage: 18.2 MB, less than 19.85% of C++ online submissions for The Skyline Problem.
99//time: O(NlogN), space: O(N)
100class Solution {
101public:
102 vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
103 int OPEN = 0, CLOSE = 1;
104 //(height, x-coord, right boundary)
105 vector<vector<int>> points;
106
107 for(int i = 0; i < buildings.size(); ++i){
108 points.push_back({buildings[i][2], buildings[i][0], buildings[i][1]});
109 points.push_back({buildings[i][2], buildings[i][1], buildings[i][1]});
110 }
111
112 //sort by x-coordinate
113 sort(points.begin(), points.end(),
114 [](const vector<int>& a, const vector<int>& b){
115 return a[1] < b[1];
116 });
117
118 //max height on top
119 priority_queue<vector<int>, vector<vector<int>>> pq;
120 vector<vector<int>> ans;
121
122 for(vector<int>& point : points){
123 int x = point[1];
124 bool isClose = (point[1] == point[2]);
125 // cout << "===x: " << x << ", left: " << !isClose << "===" << endl;
126
127 /*
128 building whose right boundary <= x should be cleared
129 */
130 // if(!pq.empty()){
131 // cout << "pq top x: " << pq.top()[1] << ", h: " << pq.top()[0] << endl;
132 // }
133
134 // cout << "push x: " << x << ", h: " << point[0] << endl;
135 pq.push(point);
136
137 //pop buildings whose right boundary <= current x-coord
138 while(!pq.empty() && /*pq.top()[2] == pq.top()[1] &&*/ pq.top()[2] <= x){
139 // cout << "pop x: " << pq.top()[1] << ", h: " << pq.top()[0] << endl;
140 pq.pop();
141 }
142
143 // cout << "pq: " << pq.size() << endl;
144
145 int height = pq.empty() ? 0 : pq.top()[0];
146 //don't pop from pq! since it could still be active!
147
148 if(ans.empty()){
149 ans.push_back({x, height});
150 // cout << "add " << x << ", " << height << endl;
151 }else if(x == ans.back()[0]){
152 /*
153 [[0,2,3],[2,5,3]]
154 */
155 if(ans.size() >= 2 && ans[ans.size()-2][1] == max(ans.back()[1], height)){
156 // cout << "erase " << ans.back()[0] << ", " << ans.back()[1] << endl;
157 ans.erase(ans.begin()+ans.size()-1);
158 // cout << "update " << x << ", " << height << endl;
159 }else{
160 ans.back()[1] = max(ans.back()[1], height);
161 }
162 }else if(ans.back()[1] != height){
163 // cout << "add " << x << ", " << height << endl;
164 ans.push_back({x, height});
165 }
166 }
167
168 return ans;
169 }
170};
171
172//line sweep + heap with remove()
173//https://briangordon.github.io/2014/08/the-skyline-problem.html
174//https://leetcode.com/problems/the-skyline-problem/discuss/61197/(Guaranteed)-Really-Detailed-and-Good-(Perfect)-Explanation-of-The-Skyline-Problem/62461
175//TLE
176class compare_height{
177public:
178 compare_height(){}
179 bool operator() (const vector<int>& b1, const vector<int>& b2) const{
180 return b1[2] < b2[2];
181 }
182};
183
184//equip the original priority_queue with "remove"
185template<typename T>
186class custom_priority_queue : public std::priority_queue<T, std::vector<T>, compare_height>{
187public:
188 bool remove(const T& value) {
189 auto it = std::find(this->c.begin(), this->c.end(), value);
190 if (it != this->c.end()) {
191 this->c.erase(it);
192 std::make_heap(this->c.begin(), this->c.end(), this->comp);
193 return true;
194 } else {
195 return false;
196 }
197 }
198};
199
200class Solution {
201public:
202 vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
203 //points sorted by their x-coord
204 map<int, vector<vector<int>>> points;
205
206 for(vector<int>& building : buildings){
207 points[building[0]].push_back(building);
208 points[building[1]].push_back(building);
209 }
210
211 custom_priority_queue<vector<int>> pq;
212
213 vector<vector<int>> ans;
214
215 for(auto it = points.begin(); it != points.end(); ++it){
216 int x = it->first;
217 vector<vector<int>> bs = it->second;
218
219 //update heap
220 for(vector<int>& b : bs){
221 if(x == b[0]){
222 //left edge
223 pq.push(b);
224 }else{
225 //x == b[1], right edge
226 pq.remove(b);
227 }
228 }
229
230 //update ans
231 if(pq.empty()){
232 ans.push_back({x, 0});
233 }else{
234 int h = pq.top()[2];
235 if(ans.empty() || h != ans.back()[1]){
236 ans.push_back({x, h});
237 }
238 }
239 }
240
241 return ans;
242 }
243};
244
245//line sweep + heap, optimized
246//Runtime: 152 ms, faster than 15.75% of C++ online submissions for The Skyline Problem.
247//Memory Usage: 21.6 MB, less than 9.56% of C++ online submissions for The Skyline Problem.
248class Solution {
249public:
250 vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
251 //points sorted by their x-coord
252 map<int, vector<vector<int>>> points;
253
254 for(vector<int>& building : buildings){
255 points[building[0]].push_back(building);
256 points[building[1]].push_back(building);
257 }
258
259 //building with larger height will be put on top
260 auto comp = [](const vector<int>& b1, const vector<int>& b2){
261 return b1[2] < b2[2];
262 };
263
264 priority_queue<vector<int>, vector<vector<int>>, decltype(comp)> pq(comp);
265
266 vector<vector<int>> ans;
267
268 for(auto it = points.begin(); it != points.end(); ++it){
269 int x = it->first;
270 vector<vector<int>> bs = it->second;
271
272 //update heap
273 for(vector<int>& b : bs){
274 if(x == b[0]){
275 //left edge
276 pq.push(b);
277 }else{
278 //x == b[1], right edge
279 // pq.remove(b);
280 }
281 }
282
283 /*
284 when you hit the right edge of a building
285 you pop nodes off the top of the heap repeatedly
286 until the top node is a building
287 whose right edge is still ahead.
288 */
289 while(!pq.empty() && pq.top()[1] <= x){
290 pq.pop();
291 }
292
293 //update ans
294 if(pq.empty()){
295 ans.push_back({x, 0});
296 }else{
297 int h = pq.top()[2];
298 if(ans.empty() || h != ans.back()[1]){
299 ans.push_back({x, h});
300 }
301 }
302 }
303
304 return ans;
305 }
306};
307
308//line sweep + multiset
309//multiset: elements are sorted, and have O(logN) "find" function
310//https://leetcode.com/problems/the-skyline-problem/discuss/61197/(Guaranteed)-Really-Detailed-and-Good-(Perfect)-Explanation-of-The-Skyline-Problem/62455
311//Runtime: 124 ms, faster than 29.41% of C++ online submissions for The Skyline Problem.
312//Memory Usage: 18 MB, less than 20.70% of C++ online submissions for The Skyline Problem.
313class Solution {
314public:
315 vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
316 //always sorted
317 multiset<vector<int>> points;
318
319 for(vector<int>& building : buildings){
320 //negative height marks left boundary
321 points.insert({building[0], -building[2]});
322 points.insert({building[1], building[2]});
323 }
324
325 /*
326 works just like the priority queue,
327 but equipped with O(logN) "find" function
328 */
329 multiset<int> heights;
330 vector<vector<int>> ans;
331
332 for(const vector<int>& point : points){
333 if(point[1] < 0){
334 //left boundary
335 heights.insert(-point[1]);
336 }else{
337 /*
338 meet right boundary,
339 erase previously inserted left boundary
340 */
341 heights.erase(heights.find(point[1]));
342 }
343
344 if(heights.empty()){
345 ans.push_back({point[0], 0});
346 }else{
347 int h = *heights.rbegin();
348 if(ans.empty() || h != ans.back()[1]){
349 ans.push_back({point[0], h});
350 }
351 }
352 }
353
354 return ans;
355 }
356};
357
358//segment tree
359//https://leetcode.com/problems/the-skyline-problem/discuss/61313/A-segment-tree-solution/185639
360//TLE
361//35 / 36 test cases passed.
362class SegTree{
363public:
364 vector<int> tree;
365
366 SegTree(int n){
367 //tree[0] is meaningless
368 //tree[1] is meaningful
369 tree = vector<int>(n);
370 }
371
372 void update(int treeIdx, int left, int right, int qleft, int qright, int val){
373 if(left > right || qright < left || qleft > right){
374 /*
375 left > right: looking at wrong range
376 qright < left || qleft > right:
377 looking range and query range has no intersection
378 */
379 return;
380 }
381
382 // cout << "tree(" << treeIdx << ") covers [" << left << ", " << right << "], query for " << "[" << qleft << ", " << qright << "], val: " << val << endl;
383
384 if(left == right){
385 //stop when the node is a leaf(it covers length-1 range)
386 //need to take max because a node can be updated multiple times!
387 tree[treeIdx] = max(tree[treeIdx], val);
388 }else{
389 int mid = (left + right) >> 1;
390
391 /*
392 current node range: [left, right]
393 left subtree range: [left, mid]
394 right subtree range: [mid+1, right]
395 */
396
397 if(qright <= mid){
398 //query range completely in left subtree
399 // cout << "complete in left subtree" << endl;
400 update(treeIdx << 1, left, mid, qleft, qright, val);
401 /*
402 need to update the internal node so that
403 it represents for the max in the range it covers
404 */
405 tree[treeIdx] = max(tree[treeIdx], tree[treeIdx << 1]);
406 }else if(qleft > mid){
407 //query range completely in right subtree
408 // // cout << "complete in right subtree" << endl;
409 update(treeIdx << 1 | 1, mid+1, right, qleft, qright, val);
410 tree[treeIdx] = max(tree[treeIdx], tree[treeIdx << 1 | 1]);
411 }else{
412 //query range cross left and right subtree
413
414 //note: qright becomes mid
415 // cout << "first go to left subtree" << endl;
416 update(treeIdx << 1, left, mid, qleft, mid, val);
417
418 //note: qleft becoems mid+1
419 // cout << "then go to right subtree" << endl;
420 update(treeIdx << 1 | 1, mid+1, right, mid+1, qright, val);
421 tree[treeIdx] = max({tree[treeIdx], tree[treeIdx << 1], tree[treeIdx << 1 | 1]});
422 }
423
424 /*
425 or simply
426 update(treeIdx << 1, left, mid, qleft, min(mid, qright), val);
427 update(treeIdx << 1 | 1, mid+1, right, max(mid+1, qleft), qright, val);
428 tree[treeIdx] = max({tree[treeIdx], tree[treeIdx << 1], tree[treeIdx << 1 | 1]});
429 */
430 }
431
432 }
433
434 int query(int treeIdx, int left, int right, int qIdx){
435 if(left > qIdx || right < qIdx) return -1;
436
437 // cout << "tree(" << treeIdx << ") covers [" << left << ", " << right << "], query for " << qIdx << endl;
438
439 if(left == right){
440 //stop when the node is a leaf(it covers length-1 range)
441 /*
442 it can be optimized by stopping at internal nodes?
443 not in this problem, because our query interval is always length one!
444 */
445 // cout << "tree(" << treeIdx << "), arr(" << left << ") val: " << tree[treeIdx] << endl;
446 return tree[treeIdx];
447 }
448
449 int mid = (left + right) >> 1;
450
451 if(qIdx <= mid){
452 int res = query(treeIdx << 1, left, mid, qIdx);
453 // cout << "tree(" << treeIdx << ") val: " << res << endl;
454 /*
455 different than lazy version,
456 don't need to take max of tree[treeIdx] and this subresult!
457 */
458 return res;
459 }else if(qIdx > mid){
460 int res = query(treeIdx << 1 | 1, mid+1, right, qIdx);
461 // cout << "tree(" << treeIdx << ") val: " << res << endl;
462 return res;
463 }
464
465 return -1;
466 }
467};
468
469class Solution {
470public:
471 vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
472 //its elements are sorted!
473 set<int> points;
474
475 for(vector<int>& b : buildings){
476 points.insert(b[0]);
477 points.insert(b[1]);
478 }
479
480 unordered_map<int, int> fw, bw;
481 int n = 0;
482
483 for(const int& point : points){
484 fw[point] = n;
485 bw[n] = point;
486 // cout << n << " <---> " << point << endl;
487 ++n;
488 }
489
490 SegTree* tree = new SegTree(n << 4);
491
492 for(vector<int>& b : buildings){
493 //tree[1]: seg tree's root
494 //[0,n-1]: range covered by current node
495 /*
496 only update the range[b's left, b's right-1],
497 note that we don't set b's right to b[2]!
498 */
499 // cout << "========" << endl;
500 tree->update(1, 0, n-1, fw[b[0]], fw[b[1]]-1, b[2]);
501 }
502
503 //build ans
504 vector<vector<int>> ans;
505
506 int preH = INT_MIN, h;
507
508 for(int i = 0; i < n; ++i){
509 // cout << "========" << endl;
510 //qeury in [0, n-1] for "i"th critical point
511 h = tree->query(1, 0, n-1, i);
512 //ignore different
513 if(h == preH) continue;
514 ans.push_back({bw[i], h});
515 preH = h;
516 }
517
518 return ans;
519 }
520};
521
522//segment tree with lazy propagation
523//https://leetcode.com/problems/the-skyline-problem/discuss/61313/A-segment-tree-solution/185639
524//Runtime: 120 ms, faster than 32.77% of C++ online submissions for The Skyline Problem.
525//Memory Usage: 17.4 MB, less than 24.52% of C++ online submissions for The Skyline Problem.
526class SegTree{
527public:
528 vector<int> tree;
529
530 SegTree(int n){
531 tree = vector<int>(n);
532 }
533
534 void update(int treeIdx, int left, int right, int qleft, int qright, int val){
535 if(left > right || qright < left || qleft > right){
536 return;
537 }
538
539 // cout << "tree(" << treeIdx << ") covers [" << left << ", " << right << "], query for " << "[" << qleft << ", " << qright << "], val: " << val << endl;
540
541 if(left == qleft && right == qright){
542 /*
543 not lazy version stops when left == right
544 (a leaf node)
545
546 lazy propagation: stop updating when
547 looking range matches update range
548 (so it may stop at interval nodes)
549 */
550 //take max because a node can be updated multiple times
551 tree[treeIdx] = max(tree[treeIdx], val);
552 }else{
553 int mid = (left + right) >> 1;
554
555 if(qright <= mid){
556 // cout << "complete in left subtree" << endl;
557 update(treeIdx << 1, left, mid, qleft, qright, val);
558 }else if(qleft > mid){
559 // // cout << "complete in right subtree" << endl;
560 update(treeIdx << 1 | 1, mid+1, right, qleft, qright, val);
561 }else{
562 // cout << "first go to left subtree" << endl;
563 update(treeIdx << 1, left, mid, qleft, mid, val);
564
565 // cout << "then go to right subtree" << endl;
566 update(treeIdx << 1 | 1, mid+1, right, mid+1, qright, val);
567 }
568
569 /*
570 or simply
571 update(treeIdx << 1, left, mid, qleft, min(mid, qright), val);
572 update(treeIdx << 1 | 1, mid+1, right, max(mid+1, qleft), qright, val);
573 */
574 }
575
576 // cout << "tree(" << treeIdx << ") covers [" << left << ", " << right << "], query for " << "[" << qleft << ", " << qright << "], set to: " << val << endl;
577 }
578
579 int query(int treeIdx, int left, int right, int qIdx){
580 if(left > qIdx || right < qIdx) return -1;
581
582 // cout << "tree(" << treeIdx << ") covers [" << left << ", " << right << "], query for " << qIdx << endl;
583
584 if(left == right){
585 /*
586 for lazy version,
587 we can't stop query until
588 we are at a leaf node
589 */
590 // cout << "tree(" << treeIdx << "), arr(" << left << ") val: " << tree[treeIdx] << endl;
591 return tree[treeIdx];
592 }
593
594 int mid = (left + right) >> 1;
595
596 int res;
597
598 /*
599 lazy propagation
600 query in left subtree or right subtree,
601 cannot return directly after return from subtree
602 */
603 if(qIdx <= mid){
604 res = query(treeIdx << 1, left, mid, qIdx);
605 // cout << "tree(" << treeIdx << ") val: " << max(tree[treeIdx], res) << endl;
606 }else if(qIdx > mid){
607 res = query(treeIdx << 1 | 1, mid+1, right, qIdx);
608 // cout << "tree(" << treeIdx << ") val: " << max(tree[treeIdx], res) << endl;
609 }
610
611 // cout << "tree(" << treeIdx << "), arr(" << left << ", " << right << ") val: " << max(tree[treeIdx], res) << endl;
612 // cout << "tree(" << treeIdx << "), arr(" << left << ", " << right << ") val: " << res << endl;
613 /*
614 for interval nodes,
615 we don't update its value if
616 the update range doesn't perfectly match its coverage
617 (this can be confirmed in "left != right" part,
618 in which we don't update tree[treeIdx]!)
619
620 so while querying, only looking at a interval node
621 is not enough to determine the range max,
622 we need to go through all of its leaves
623 to determine the range max!!
624 */
625 return max(tree[treeIdx], res);
626 }
627};
628
629class Solution {
630public:
631 vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
632 set<int> points;
633
634 for(vector<int>& b : buildings){
635 points.insert(b[0]);
636 points.insert(b[1]);
637 }
638
639 unordered_map<int, int> fw, bw;
640 int n = 0;
641
642 for(const int& point : points){
643 fw[point] = n;
644 bw[n] = point;
645 // cout << n << " <---> " << point << endl;
646 ++n;
647 }
648
649 SegTree* tree = new SegTree(n << 4);
650
651 for(vector<int>& b : buildings){
652 // cout << "========" << endl;
653 tree->update(1, 0, n-1, fw[b[0]], fw[b[1]]-1, b[2]);
654 }
655
656 vector<vector<int>> ans;
657
658 int preH = INT_MIN, h;
659
660 for(int i = 0; i < n; ++i){
661 // cout << "========" << endl;
662 h = tree->query(1, 0, n-1, i);
663 if(h == preH) continue;
664 ans.push_back({bw[i], h});
665 preH = h;
666 }
667
668 return ans;
669 }
670};
671
672//binary indexed tree(not understand?)
673//https://leetcode.com/problems/the-skyline-problem/discuss/61198/My-O(nlogn)-solution-using-Binary-Indexed-Tree(BIT)Fenwick-Tree/62473
674//Runtime: 136 ms, faster than 22.81% of C++ online submissions for The Skyline Problem.
675//Memory Usage: 17.2 MB, less than 28.04% of C++ online submissions for The Skyline Problem.
676class Solution {
677public:
678 /*
679 here the direction of "add" and "find" are
680 opposite to that in "307. Range Sum Query - Mutable Medium",
681 that's because here the interval node is
682 the summary of itself and its right child?
683 (not left child just like "307"?)
684 */
685 void add(vector<int>& BIT, int i, int h){
686 //i is already BIT's index, not nums's
687
688 while(i > 0){
689 BIT[i] = max(BIT[i], h);
690 // cout << "BIT[" << i << "]: " << BIT[i] << endl;
691 i -= i&(-i);
692 }
693 };
694
695 int find(vector<int>& BIT, int i){
696 //i is already BIT's index, not nums's
697
698 int h = 0;
699
700 while(i < BIT.size()){
701 h = max(h, BIT[i]);
702 // cout << "BIT[" << i << "]: " << BIT[i] << endl;
703 i += i&(-i);
704 }
705
706 return h;
707 };
708
709 vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
710 vector<vector<int>> points;
711 int OPEN = 0, CLOSE = 1;
712
713 for(int i = 0; i < buildings.size(); ++i){
714 points.push_back({buildings[i][0], OPEN, i});
715 points.push_back({buildings[i][1], CLOSE, i});
716 }
717
718 //sort by OPEN and CLOSE is important!!
719 //otherwise it fails the testcase "[[0,2,3],[2,5,3]]"
720 sort(points.begin(), points.end(),
721 [](vector<int>& a, vector<int>& b){
722 return a[0] == b[0] ? a[1] < b[1] : a[0] < b[0];
723 });
724
725 unordered_map<int, int> fw;
726 int n = 1;
727
728 //index starts from 1, aligned with "BIT"!!
729 for(const vector<int>& point : points){
730 fw[point[0]] = n;
731 // cout << n << " <---> " << point[0] << endl;
732 ++n;
733 }
734
735 vector<int> BIT(n+1);
736
737 vector<vector<int>> ans;
738
739 int preH = INT_MIN, h;
740
741 for(const vector<int>& point : points){
742 // cout << "========" << endl;
743 // cout << "x: " << point[0] << endl;
744 if(point[1] == OPEN){
745 //only update BIT when we meet left boundary
746 //set "arr[fw[point[1]]-1]" to the building's height
747 //-1 because right boundary won't contribute to skyline
748 // cout << "add: (" << fw[point[1]]-1 << ", " << point[2] << ")" << endl;
749 add(BIT, fw[buildings[point[2]][1]]-1, buildings[point[2]][2]);
750 }
751 // cout << "========" << endl;
752 //query for current x-coord
753 h = find(BIT, fw[point[0]]);
754 // cout << "query: " << fw[point[0]] << " -> " << h << endl;
755 if(h == preH) continue;
756 if(!ans.empty() && ans.back()[0] == point[0]){
757 ans.back()[1] = max(ans.back()[1], h);
758 }else{
759 ans.push_back({point[0], h});
760 }
761 preH = h;
762 }
763
764 return ans;
765 }
766};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.