# C++ O(NlogN) solution with map

• The idea is using a map<int, int, greater<int>> m to maintain the height and right position. For each new building, before insert the <height, right> to the map, check current the highest buildings right position, if it result skyline change, add it to result.

class Solution {
public:
vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
map<int, int, greater<int>> m;
vector<pair<int, int>> res;
for (auto b : buildings) {
int l = b[0], r = b[1], h = b[2];
helper(res, m, l);
m[h] = max(m[h], r);
if (res.empty() || m.begin()->first > res.back().second) {
if (!res.empty() && l == res.back().first) {
res.back().second = m.begin()->first;
}
else {
res.emplace_back(l, m.begin()->first);
}
}
}
helper(res, m, 0);
return res;
}

void helper(vector<pair<int, int>>& r, map<int, int, greater<int>>& m, int limit) {
int x = 0;
while (!m.empty() && (!limit || m.begin()->second < limit)) {
x = max(x, m.begin()->second);
m.erase(m.begin());
// Only put to result the current right pos is larger than the previous one
if (m.empty() || m.begin()->second > x) {
r.emplace_back(x, m.empty() ? 0 : m.begin()->first);
}
}
}
};

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