64ms, Runtime beats 100% of cpp submissions


  • 0
    K
    class Solution {
        class edge {
        public:
            int x;
            int height;
            bool isLeft;
            edge(){}
            edge(int a, int b, bool c):
                x(a), height(b), isLeft(c) {
            }
        };
        
        static bool compare(edge const& lhs, edge const& rhs) {
            if(lhs.x != rhs.x) {
                return lhs.x < rhs.x;
            }
            if(lhs.isLeft and rhs.isLeft) {
                return lhs.height > rhs.height;
            }
            
            if(!lhs.isLeft and !rhs.isLeft) {
                return lhs.height < rhs.height;
            }
            
            return lhs.isLeft;
        }
    public:
        vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
            vector<pair<int, int>> result;
            if(buildings.empty()) return result;
            int n = (int)buildings.size();
            multiset<int> H;
            vector<edge> edges;
            for(int i = 0; i < n; ++i) {
                edges.push_back(edge(buildings[i][0], buildings[i][2], true));
                edges.push_back(edge(buildings[i][1], buildings[i][2], false));
            }
            sort(edges.begin(), edges.end(), compare);
            
            // solution #1
            /*
            for(int i = 0; i < (int)edges.size(); ++i) {
                if(edges[i].isLeft) {
                    if(H.empty() or edges[i].height > *(--H.end())) {
                        result.push_back({edges[i].x, edges[i].height});
                    }
                    H.insert(edges[i].height);
                } else {
                    H.erase(H.find(edges[i].height));
                    if(H.empty()) {
                        result.push_back({edges[i].x, 0});
                    }
                    else if(edges[i].height > *(--H.end())) {
                        result.push_back({edges[i].x, *(--H.end())});
                    }
                }
            }
            */
            
            // solution #2
            int prev = 0;
            for(int i = 0; i < (int)edges.size(); ++i) {
                if(edges[i].isLeft) {
                    H.insert(edges[i].height);
                } else {
                    H.erase(H.find(edges[i].height));
                }
                int curr = (H.empty() ? 0 : *(--H.end()));
                if(curr != prev) {
                    result.push_back({edges[i].x, curr});
                    prev = curr;
                }
            }
                
            return result;
        }
    };

  • 1
    Y

    The "huge margin" is an artifact -- apparently the OJ changed its timing measurement but did not update the data/histogram for previous submissions. If you just take any passable solution from discuss and submit it, you'd get "beating 100.00% of cppsubmissions". :)


  • 0
    K

    I didn't know. Thanks.


Log in to reply
 

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