# 36 ms C++ solution using map and beating 99.8%

• Iteratively add a new building and update a map which stores key points directly. For each new building, find a range of influenced key points and update them. For convenience, an auxiliary key point (-1, 0) is used.

The worst-case complexity is O(n^2), and can be improved to O(n log n) if sorting the buildings by the width (Ri - Li). Here, sorting takes O(n log n) and the following takes O(n). However, constant will be big and test cases are mostly "not so bad".

``````class Solution {
public:
vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
map<int, int> keyPoints;
keyPoints.insert(pair<int, int>(-1, 0));
for (const auto& building : buildings)
{
int left = building[0], right = building[1], height = building[2];
auto firstKey = prev(keyPoints.upper_bound(left)); // <= left
auto lastKey = prev(keyPoints.lower_bound(right)); // < right
bool pre = firstKey != keyPoints.begin() && prev(firstKey)->second == height;

if (firstKey == lastKey) {
if (firstKey->second < height) {
keyPoints.insert(firstKey, { right, firstKey->second });
if (firstKey->first == left) {
if (pre) keyPoints.erase(firstKey); // erase
else firstKey->second = height; // raise up
}
else keyPoints.insert(firstKey, { left, height }); // insert a new kp
}
}
else{
// FIRST ( first one <= left )
if (firstKey->second < height) {
if (firstKey->first == left) {
if (pre) keyPoints.erase(firstKey); // erase
else firstKey->second = height; // raise up
}
else firstKey = keyPoints.insert(firstKey, { left, height }); // insert a new kp
}

// MIDDLE ( left < ... < right )
pre = firstKey->second <= height;
auto iKey = next(firstKey);
while (iKey != lastKey) {
bool cur = iKey->second <= height;
if (cur) {
if (pre) iKey = keyPoints.erase(iKey); // erase
else { // raise up
iKey->second = height;
++iKey;
}
}
else ++iKey;
pre = cur;
}

// LAST ( first one < right )
if (lastKey->second < height) { // move
keyPoints.insert(lastKey, { right, lastKey->second });
if (pre) keyPoints.erase(lastKey);
else lastKey->second = height;
}
}
}
vector<pair<int, int>> result;
auto iKey = next(keyPoints.begin());
for (; iKey != keyPoints.end(); ++iKey)
result.push_back(*iKey);
return result;
}
};
``````

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