blob: 1828978829500d977fc296b9d362a48bafca706a (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include "leetcode.h"
class Solution {
public:
vvd(int) getSkyline(vvd(int) & buildings) {
vvd(int) ans;
map<int, vector<pair<int, int>>> mvp;
for (auto &b : buildings) {
mvp[b[0]].push_back({b[2], 0});
mvp[b[1]].push_back({b[2], 1});
}
multiset<int> m;
for (auto &[pos, heights] : mvp) {
for (auto &[height, type] : heights) {
if (type == 0)
m.insert(height);
else
m.erase(m.find(height));
}
int newHeight = m.empty() ? 0 : *m.begin();
if (!ans.empty() && ans.back()[1] == newHeight)
continue;
else
ans.push_back(vector<int>({pos, newHeight}));
}
return ans;
}
};
|