# The Skyline Problem Solutions in C++

Number 218

Difficulty Hard

Acceptance 34.6%

Link LeetCode

Other languages —

## Solutions

### C++ solution by haoel/leetcode

// Source : https://leetcode.com/problems/the-skyline-problem/// Author : Hao Chen// Date : 2015-06-11/** Sweep line with max-heap* ------------------------* Notice that "key points" are either the left or right edges of the buildings.** Therefore, we first obtain both the edges of all the N buildings, and store the 2N edges in a sorted array.* Maintain a max-heap of building heights while scanning through the edge array:* 1) If the current edge is a left edge, then add the height of its associated building to the max-heap;* 2) If the edge is a right one, remove the associated height from the heap.** Then we take the top value of the heap (yi) as the maximum height at the current edge position (xi).* Now (xi, yi) is a potential key point.** If yi is the same as the height of the last key point in the result list, it means that this key point* is not a REAL key point, but rather a horizontal continuation of the last point, so it should be discarded;** otherwise, we add (xi,yi) to the result list because it is a real key point.** Repeat this process until all the edges are checked.** It takes O(NlogN) time to sort the edge array. For each of the 2N edges,* it takes O(1) time to query the maximum height but O(logN) time to add* or remove elements. Overall, this solution takes O(NlogN) time.*/class Solution {public:vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {vector< pair<int, int> > edges;//put all of edge into a vector//set left edge as negtive, right edge as positive//so, when we sort the edges,// 1) for same left point, the height would be descending order// 2) for same right point, the height would be ascending orderint left, right, height;for(int i=0; i<buildings.size(); i++) {left = buildings[i][0];right = buildings[i][1];height = buildings[i][2];edges.push_back(make_pair(left, -height));edges.push_back(make_pair(right, height));}sort(edges.begin(), edges.end());// 1) if we meet a left edge, then we add its height into a `set`.// the `set` whould sort the height automatically.// 2) if we meet a right edge, then we remove its height from the `set`//// So, we could get the current highest height from the `set`, if the// current height is different with preivous height, then we need add// it into the result.vector< pair<int, int> > result;multiset<int> m;m.insert(0);int pre = 0, cur = 0;for (int i=0; i<edges.size(); i++){pair<int,int> &e = edges[i];if (e.second < 0) {m.insert(-e.second);}else{m.erase(m.find(e.second));}cur = *m.rbegin();if (cur != pre) {result.push_back(make_pair(e.first, cur));pre = cur;}}return result;}};