36 ms C++ solution using map and beating 99.8%


  • 0
    G

    Iteratively add a new building and update a map which stores key points directly. For each new building, find a range of influenced key points and update them. For convenience, an auxiliary key point (-1, 0) is used.

    The worst-case complexity is O(n^2), and can be improved to O(n log n) if sorting the buildings by the width (Ri - Li). Here, sorting takes O(n log n) and the following takes O(n). However, constant will be big and test cases are mostly "not so bad".

    class Solution {
    public:
      vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
        map<int, int> keyPoints;
        keyPoints.insert(pair<int, int>(-1, 0));
        for (const auto& building : buildings)
        {
          int left = building[0], right = building[1], height = building[2];
          auto firstKey = prev(keyPoints.upper_bound(left)); // <= left
          auto lastKey = prev(keyPoints.lower_bound(right)); // < right
          bool pre = firstKey != keyPoints.begin() && prev(firstKey)->second == height;
          
          if (firstKey == lastKey) {
            if (firstKey->second < height) {
              keyPoints.insert(firstKey, { right, firstKey->second });
              if (firstKey->first == left) {
                if (pre) keyPoints.erase(firstKey); // erase
                else firstKey->second = height; // raise up
              }
              else keyPoints.insert(firstKey, { left, height }); // insert a new kp
            }
          }
          else{
            // FIRST ( first one <= left )
            if (firstKey->second < height) {
              if (firstKey->first == left) {
                if (pre) keyPoints.erase(firstKey); // erase
                else firstKey->second = height; // raise up
              }
              else firstKey = keyPoints.insert(firstKey, { left, height }); // insert a new kp
            }
    
            // MIDDLE ( left < ... < right )
            pre = firstKey->second <= height;
            auto iKey = next(firstKey);
            while (iKey != lastKey) {
              bool cur = iKey->second <= height;
              if (cur) {
                if (pre) iKey = keyPoints.erase(iKey); // erase
                else { // raise up
                  iKey->second = height;
                  ++iKey;
                }
              }
              else ++iKey;
              pre = cur;
            }
    
            // LAST ( first one < right )
            if (lastKey->second < height) { // move
              keyPoints.insert(lastKey, { right, lastKey->second });
              if (pre) keyPoints.erase(lastKey); 
              else lastKey->second = height;
            }
          }
        }
        vector<pair<int, int>> result;
        auto iKey = next(keyPoints.begin());
        for (; iKey != keyPoints.end(); ++iKey)
          result.push_back(*iKey);
        return result;
      }
    };
    

Log in to reply
 

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