leetcode

0 class Solution {

1 public:

2 vector<vector<int>> getSkyline(const vector<vector<int>> &buildings) const {

3 using type_t = tuple<int, int>;

4 vector<type_t> vec;

5 vec.reserve(2 * size(buildings) + 1);

6

7 for (const auto &building : buildings) {

8 vec.emplace_back(building[0], +building[2]);

9 vec.emplace_back(building[1], -building[2]);

10 }

11 sort(begin(vec), end(vec));

12 vec.emplace_back(-1, -1);

13

14 multiset<int> st = {{0}};

15 vector<vector<int>> res;

16 for (int i = 0; i < size(vec) - 1; i++) {

17 const auto [x, h] = vec[i];

18

19 if (h > 0)

20 st.insert(h);

21 else

22 st.extract(-h);

23

24 if (x != get<0>(vec[i + 1])) {

25 const int height = *st.rbegin(); // 0 will always be there

26 if (res.empty() || res.back()[1] != height) res.push_back({x, height});

27 }

28 }

29

30 return res;

31 }

32 };