[recommend for beginners]clean C++ implementation with detailed explanation


  • 21
    class Solution {
    public:
        vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
            vector<pair<int, int>> edges;
            int left, right, height;
            for(int i=0; i<buildings.size(); i++){
                left=buildings[i][0];
                right=buildings[i][1];
                height=buildings[i][2];
                /*** make sure : for the same left point we use the bigger height ***/
                edges.push_back(make_pair(left, -height));
                edges.push_back(make_pair(right, height));
            }
            sort(edges.begin(), edges.end());
            vector<pair<int, int>> result;
            /*** use the multiset to store the max height util current pos ***/
            multiset<int> m;
            /*** left most height ***/
            m.insert(0);
            int pre=0, cur=0;
            for(int i=0; i<edges.size(); i++){
                pair<int, int> e=edges[i];
                if(e.second < 0)  m.insert(-e.second);
                else m.erase(m.find(e.second));
                cur=*(m.rbegin());
                if(cur!=pre){
                    result.push_back(make_pair(e.first, cur));
                    pre=cur;
                }
            }
            return result;
        }
    };

  • 0
    2
    class Solution {
    public:
        vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
            vector<pair<int, int>> result;
            vector<pair<int, int>> edges;
            
            for(auto it : buildings) {
                int left = it[0];
                int right = it[1];
                int height = it[2];
                edges.push_back(make_pair(left, -height));
                edges.push_back(make_pair(right, height));
            }
            
            sort(edges.begin(), edges.end());
            
            multiset<int> m;
            int pre = 0, cur = 0;
            
            m.insert(0);
            for(auto it : edges) {
                int pos = it.first;
                int height = it.second;
                if(height < 0) { 
                    m.insert(-height);
                }
                else {
                    m.erase(m.find(height));
                }
                cur = *(m.rbegin());
                if(cur != pre) {
                    result.push_back(make_pair(pos, cur));
                    pre = cur;
                }
            }
            
            return result;
        }
    };

  • 0

    Here is the LintCode provided related Building Outline problem

    As the output format is changed , so I just change the above code to get the AC implementation ....

    Here is the CODE :

    bool compare(pair<int, int> a, pair<int, int> b) {
        return a.first == b.first ?  a.second < b.second : a.first < b.first;
    }
    class Solution {
    public:
        /**
         * @param buildings: A list of lists of integers
         * @return: Find the outline of those buildings
         */
        vector<vector<int> > buildingOutline(vector<vector<int> > &buildings) {
            // write your code here
            vector<vector<int>> result;
            vector<pair<int, int>> dict;
            int size_ = buildings.size();
            if(size_ == 0)  return result;
            
            for(int i = 0; i < size_; i++) {
                dict.push_back(make_pair(buildings[i][0], -buildings[i][2]));
                dict.push_back(make_pair(buildings[i][1], buildings[i][2]));
            }
            sort(dict.begin(), dict.end(), compare);
            
            
            multiset<int> max_height {0};
            int pre = 0;
            for(int i = 0; i < dict.size(); i++) {
                //cout<<i<<":"<<dict[i].first<<dict[i].second<<endl;
                if(dict[i].second < 0) {
                    max_height.insert(-dict[i].second);
                } else {
                    max_height.erase(max_height.find(dict[i].second));
                }
                
                int cur = *(max_height.rbegin());
                if(cur != pre) {
                    result.push_back({dict[i].first, 0, cur});
                    pre = cur;
                }
            }
            
            //cout<<result.size()<<endl;
            for(int i = 0; i < result.size() - 1; i++) {
                result[i][1] = result[i+1][0];
            }
    
            vector<vector<int>> outline;
            for(int i = 0; i < result.size(); i++) {
                if(result[i][2] != 0)  outline.push_back(result[i]);
            }
            return outline;
        }
    };

  • 0
    Z

    Using multiset is a great idea! Much easier to understand than using a heap.


  • 0

    You are right !


  • 0
    F

    the key idea is how to sort the array by position and height, and then just keep it by processing a heap


  • 1
    F
    This post is deleted!

  • 1
    F
    
    class Solution {
    public:
        vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
            vector<pair<int, int> > h, res;
            multiset<int> m;
            int pre = 0, cur = 0;
            for (auto &a : buildings) {
                h.push_back({a[0], -a[2]});
                h.push_back({a[1], a[2]});
            }
            sort(h.begin(), h.end());
            m.insert(0);
            for (auto &a : h) {
                if (a.second < 0) m.insert(-a.second);
                else m.erase(m.find(a.second));
                cur = *m.rbegin();
                if (cur != pre) {
                    res.push_back({a.first, cur});
                    pre = cur;
                }
            }
            return res;
        }
    };
    

  • 0
    T
    This post is deleted!

  • 0
    L

    Nice solution. My first thinking was about to write a hash heap and soon got headache for that. Using multiset make things much easier!


Log in to reply
 

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