28 line of Code, My C++ solution (840ms) O(NlogN) with multiset and multimap


  • 7

    The basic idea is:
    1.put the start and end of each rectangle into a multimap, we will scan it later. The second parameter of the pair is its height.(i.e. as for [0,5,3] we will put {0, 3} and {5, -3} into the map)
    2.for each element in multimap, if the height is greater than zero, we put it into multiset, else we find and erase it from the set.

    1. the multiset means at each x value, the existing rectangle.
    2. After processing each x value, the max in the set is what we need, just put it into the vector.
    class Solution {
    public:
        struct comp{
            bool operator ()(const int &a, const int &b){ return a > b;}
        };
        
        vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
            vector<pair<int, int> > ret;
            multimap<int, int> mii;
            for (int i = 0; i < buildings.size(); ++i){
                vector<int> &vi = buildings[i];
                mii.insert(make_pair(vi[0], vi[2]));
                mii.insert(make_pair(vi[1], vi[2] * -1));
            }
            multiset<int, comp> msi;
            msi.insert(0);
            while (mii.size()){
                int last_height = *msi.begin();
                int cur = mii.begin()->first;
                while (mii.begin()->first == cur){
                    int height = mii.begin()->second;
                    if (height > 0){
                        msi.insert(height);
                    }else{
                        msi.erase(msi.find(height * -1));
                    }
                    mii.erase(mii.begin());
                }
                if (*msi.begin() != last_height){
                    ret.push_back(make_pair(cur, *msi.begin()));
                }
            }
            return ret;
        }
    };

  • 0
    This post is deleted!

  • 0

    It works! Thank you


  • 0

    Hey 西兑, Your code is really easy to understand and good solution. Use -vi[2] to distinguish left and right point. Use the thinking of there must have a left point to pair the right point.

    I have met the similar solution on this blog: http://www.cnblogs.com/easonliu/p/4531020.html


  • 0

    Yeah, what you received is just what I thought~ I am happy that my code is easy to understand~
    The basic thought of the blog is the same to mine, but we chose different data structure. He used the new feature of c++ and made more encapsulation, really cool~


Log in to reply
 

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