# C++ O(N*logN) solution using a multiset

• ``````    vector<pair<int, int>> getSkyline(vector<vector<int>>& blg) {

vector<vector<int>> points;
for (auto& b : blg) { // O(N)
points.push_back({ b[0], -b[2] }); // start point
points.push_back({ b[1],  b[2] }); // end point
}
sort(points.begin(), points.end(), // O(N*logN)
[](vector<int>& a, vector<int>& b)
{ return a[0] != b[0]? a[0] < b[0] : a[1] < b[1]; });

vector<pair<int, int>> res;
multiset<int> s = {0}; int prevMax = 0;
for (auto& p : points) { // O(N)
(p[1] < 0)? s.insert(-p[1]) : s.erase(s.find(p[1])); // O(logN)
int curMax = *s.rbegin();
if (curMax != prevMax)
res.emplace_back(p[0], curMax), prevMax = curMax;
}

return res;
}
``````

• what's the difference between

``````s.erase(s.find(p[1]));
``````

and

``````s.erase(p[1]);
``````

?

• @kupe Note that `s` is in type `multiset`, so if erasing by value, all elements with the same value will be removed, and this is not what we intended. Instead, erasing by iterator position erases only a single element, and this does the job.

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