# C++ solution using map and unordered_set, easy to understand

• My method use two maps to store information. The first map, called pos2Heights, maps a position on x-axis to an unordered set containing all the building heights at this position. Note for right edges, the corresponding building heights have a minus sign. For example, for a input like [[1, 4, 1], [2, 3, 2], [3, 4, 3]], pos2Heights should look like:
1 --> {1}
2 --> {2}
3 --> {-2, 3}
4 --> {-1, -3}.
The second map, called heightCount, is used during the iteration of pos2Heights and records the count of each height value. Therefore, for each position x, the maximum height of heightCount after visiting the set pos2Heights[x] can reflect the height of skyline at x.

``````class Solution {
public:
vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
int n = buildings.size();
vector<pair<int, int>> res;

map<int, unordered_set<int>> pos2Heights;

for (auto& building : buildings)
{
int leftEdgePos = building[0], rightEdgePos = building[1];
int height = building[2];

pos2Heights[leftEdgePos].insert(height);
pos2Heights[rightEdgePos].insert(-height);
}

map<int, int> heightCount;
int maxHeightOld = INT_MIN;

for (auto& iter : pos2Heights)
{
int position = iter.first;

for (auto height : iter.second)
{
//left edge at this position: add height to heightCount
if (height > 0)
heightCount[height]++;
//right edge: remove height from heightCount
else
{
height = -height;
heightCount[height]--;
if (heightCount[height] == 0)
heightCount.erase(height);
}
}

// get the maximum height in heightCount
int maxHeight = 0;
if (!heightCount.empty())
maxHeight = (*(heightCount.rbegin())).first;

if (maxHeight != maxHeightOld)
res.push_back(make_pair(position, maxHeight));

maxHeightOld = maxHeight;
}

return res;
}
};
``````

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