leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0218.cpp (988B)

      1 class Solution {
      2   public:
      3     vector<vector<int>> getSkyline(const vector<vector<int>> &buildings) const {
      4         using type_t = tuple<int, int>;
      5         vector<type_t> vec;
      6         vec.reserve(2 * size(buildings) + 1);
      7 
      8         for (const auto &building : buildings) {
      9             vec.emplace_back(building[0], +building[2]);
     10             vec.emplace_back(building[1], -building[2]);
     11         }
     12         sort(begin(vec), end(vec));
     13         vec.emplace_back(-1, -1);
     14 
     15         multiset<int> st = {{0}};
     16         vector<vector<int>> res;
     17         for (int i = 0; i < size(vec) - 1; i++) {
     18             const auto [x, h] = vec[i];
     19 
     20             if (h > 0)
     21                 st.insert(h);
     22             else
     23                 st.extract(-h);
     24 
     25             if (x != get<0>(vec[i + 1])) {
     26                 const int height = *st.rbegin(); // 0 will always be there
     27                 if (res.empty() || res.back()[1] != height) res.push_back({x, height});
     28             }
     29         }
     30 
     31         return res;
     32     }
     33 };