# share a c++ solution using heap and sweeping idea

• The idea is to

1. Construct the positions where skyline may need to be updated,
This is whenever a building start or end, such vector is denoted by "vector<pair<int,int>> events" where pair.first is the
location, pair.second is the id of the building, 0~n-1 for start (left of building), -1 ~ -n for end (right of building)

2. At each location where updated needs to be checked, first add new buildings(if any) into max_heap(by its height)
when make sure finishing all events at this location, condition is ( i = n_event - 1 || x[i] < x[i+1]), get the top element
from the heap, which corresponds to the highest building.

3. Notice this building maybe invalid ( if x > buildings.right), so pop top element until finds a valid one, and its height will
be the h at the location, add to solution if h is different from previous.

``````class Solution {
public:
vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
vector<pair<int,int>> events;   // first: x, second: id, >=0 for st, <0 for nd
for(int i = 0; i < buildings.size(); i++) {
events.push_back({buildings[i][0],i});
events.push_back({buildings[i][1],-i-1});
}
sort(events.begin(), events.end());
priority_queue<vector<int>, vector<vector<int>>, pq_comp> pq;
vector<pair<int,int>> res;
for(int i = 0; i < events.size(); i++) {
int id = events[i].second, x = events[i].first;
if(id >= 0) {
pq.push(buildings[id]);
}
if(i == events.size() - 1 || x < events[i+1].first) {
while(!pq.empty() && pq.top()[1] <= events[i].first ) {
pq.pop();
}
int h = (pq.empty())?(0):(pq.top()[2]);
if(res.empty() || h != res.back().second) {
res.push_back({x, h});
}
}
}
return res;
}
private:
struct pq_comp {
bool operator() (const vector<int> &x, const vector<int> &y) {
return x[2] < y[2];
}
};
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.