# c++ O(nlogn) solution using priority queue and map

• The solution is based on the following link:

``````struct MyPair{
int x, h, i;
MyPair(int a, int b, int c): x(a), h(b), i(c) {}
};
bool operator>(MyPair p1, MyPair p2) {
return p1.x == p2.x ? p1.h * p1.i < p2.h * p2.i : p1.x > p2.x;
}
class Solution {
public:
vector<pair<int, int>> getSkyline(vector<vector<int>>& b) {
priority_queue<MyPair, vector<MyPair>, greater<MyPair>> p;
map<int, int> s;
vector<pair<int, int>> res;
for (vector<int> v : b) {
p.push(MyPair(v[0], v[2], 1));
p.push(MyPair(v[1], v[2], -1));

}
s[0] = 1;
while (p.size()) {
MyPair m = p.top();
p.pop();
int prev_max = s.rbegin()->first;
if (m.i == 1) {
s[m.h]++;
if (prev_max < s.rbegin()->first) {
res.push_back(make_pair(m.x, m.h));
}
} else {
s[m.h]--;
if (s[m.h] == 0) s.erase(m.h);
int cur_max = s.rbegin()->first;
if (cur_max != prev_max) {
res.push_back(make_pair(m.x, cur_max));
}
}
}
return res;
}
};
``````

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