# C++ Solution using multiset

• class Solution {
private:
struct Compare {
bool operator()(int x, int y) {
return x > y;
}
};
multiset<int, Compare> myset;
struct Node {
int val;
int pos;
bool is_start;
Node(int pos, int val, bool is_start) {
this -> val = val;
this -> pos = pos;
this -> is_start = is_start;
}
};
static bool compare(Node n1, Node n2) {
if(n1.pos == n2.pos) {
if(n1.is_start && n2.is_start) {
return n1.val > n2.val;
}
if(!n1.is_start && !n2.is_start) {
return n1.val < n2.val;
}
return n1.is_start;
}else {
return n1.pos < n2.pos;
}
}
void eraseset(int value) {
auto it = myset.begin();
while(it != myset.end()) {
if(*it == value) {
myset.erase(it);
break;
}
it++;
}
}
public:
vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
vector<Node> nodes;
for(auto it : buildings) {
nodes.push_back(Node(it[0], it[2], true));
nodes.push_back(Node(it[1], it[2], false));
}
sort(nodes.begin(), nodes.end(), compare);
myset.insert(0);
vector<pair<int, int>> res;
int curmax = 0;
for(auto it : nodes) {
if(it.is_start) {
if(it.val > curmax) {
curmax = it.val;
res.push_back(make_pair(it.pos, it.val));
}
myset.insert(it.val);
}else {
eraseset(it.val);
if(it.val == curmax) {
if(*myset.begin() != curmax) {
res.push_back(make_pair(it.pos, *myset.begin()));
}
curmax = *myset.begin();
}
}
}
return res;
}
};

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