leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0218.cpp (988B)

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 };