13-line C++ code using map and multiset


  • 2
    H

    Inspired by the multimap method, but want to make the logic and code simpler.
    The idea is for a given position, update the heights, insert or delete
    Then if the current maximum height changes just push the position and height into the result.

    class Solution {
    public:
        vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
            map<int, vector<int>> m;
            for(vector<int> v : buildings){
                m[v[0]].push_back(v[2]);
                m[v[1]].push_back(-v[2]);
            }
            multiset<int> s;
            s.insert(0);
            vector<pair<int, int>> res;
            for(auto it = m.begin(); it != m.end(); ++it){
                for(int height : it->second){
                    if(height > 0) s.insert(height);
                    else s.erase(s.find(-height));
                }
                if(res.empty() || *s.rbegin() != res.back().second) res.push_back({it->first, *s.rbegin()});
            }
            return res;
        }
    };

  • 0
    A

    First of all it the best solution....Using multiset for getting highest height at current point...:)

    In the else part of last for why it won't work if we give only value to erase function. I mean do we have to give its iterator every time?


  • 0
    A

    Actually we want to delete only 1 instance of that height thats why we are using iterator to delete..right?


Log in to reply
 

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