# My accepted C++ solution, 900+ ms

• Basic idea, sort all intervals, then maintain a BST while iterating for solutions.

(I must have mistaken the running time, should be 900+ ms not 300+ :-) )

``````class Solution {
public:
vector<pair<int, int> > getSkyline(vector<vector<int> >& buildings) {
map<int, vector<int> > starts;
map<int, vector<int> > ends;
set<int> points;

for(int i = 0; i < buildings.size(); ++i) {
starts[buildings[i][0]].push_back(buildings[i][2]);
ends[buildings[i][1]].push_back(buildings[i][2]);
points.insert(buildings[i][0]);
points.insert(buildings[i][1]);
}

vector<pair<int, int> > res;
pair<int, int> tResult;
map<int, int> tree;
int currMax = -1;
int currStart = -1;

for(set<int>::iterator iter = points.begin(); iter != points.end(); ++iter) {
vector<int> start = starts[*iter];
vector<int> end = ends[*iter];

for(int i = 0; i < start.size(); ++i) {
tree[start[i]]++;
}

for(int i = 0; i < end.size(); ++i) {
tree[end[i]]--;
if(tree[end[i]] == 0) {
tree.erase(end[i]);
}
}

if (tree.size() == 0){
tResult.first = *iter;
tResult.second = 0;
res.push_back(tResult);

currStart = -1;
currMax = -1;

} else {
if(currMax == -1) {
currStart = *iter;
currMax = tree.rbegin()->first;

tResult.first = currStart;
tResult.second = currMax;
res.push_back(tResult);
} else {

int max = tree.rbegin()->first;
if(max != currMax) {
currStart = *iter;
currMax = max;
tResult.first = currStart;
tResult.second = currMax;
res.push_back(tResult);
}
}
}
}
return res;
}
};``````

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