C++, very fast(22ms), kind of complicated(140 lines)


  • 0
    M
    class Solution {
    public:
        vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
            vector<pair<int, int> > res; // result
            if (buildings.size() == 0)
                return res;
            
            list<pair<int, pair<int, int> > > h_x1_x2;
            for (int i = 0; i < buildings.size(); i ++)
                h_x1_x2.push_back(make_pair(buildings[i][2], make_pair(buildings[i][0], buildings[i][1]))); // 
            
            h_x1_x2.sort(my_sort); // Sort
            
            vector<pair<int, int> > x1_x2; // store blocks' coordinate
            list<pair<int, pair<int, int> > >::iterator it = h_x1_x2.begin();
            while (it != h_x1_x2.end()) {
                const int x1 = (*it).second.first;
                const int x2 = (*it).second.second;
                if (x1_x2.size() == 0)
                    res.push_back(make_pair(x1, (*it).first));
                //=========Update Result=======
                for (int i = 0; i < x1_x2.size(); i ++) {
                    if (x1 < x1_x2[i].first && x2 > x1_x2[i].second) { // conclude several blocks
                        res.push_back(make_pair(x1, (*it).first));
                        res.push_back(make_pair(x1_x2[i].second, (*it).first));
                        i ++;
                        while (i < x1_x2.size()) {
                            if (x1_x2[i].second < x2)
                                res.push_back(make_pair(x1_x2[i].second, (*it).first));
                            i ++;
                        }
                        break;
                    }
                    if (x1 >= x1_x2[i].first && x2 <= x1_x2[i].second) // be concluded
                        break;
                    if (x1 < x1_x2[i].first && x2 <= x1_x2[i].second) { // overlap on left
                        res.push_back(make_pair(x1, (*it).first));
                        break;
                    }
                    if (x1 <= x1_x2[i].second && x2 > x1_x2[i].second) { // overlap on right
                        res.push_back(make_pair(x1_x2[i].second, (*it).first));
                        i ++;
                        while (i < x1_x2.size()) {
                            if (x1_x2[i].second < x2)
                                res.push_back(make_pair(x1_x2[i].second, (*it).first));
                            i ++;
                        }
                        break;
                    } else if (i == x1_x2.size() - 1) { // non-overlap
                        res.push_back(make_pair(x1, (*it).first));
                    }
                }
                //========end==========
                    
                Add(x1, x2, x1_x2); // Update blocks
                it ++;
            }
            for (int i = 0; i < x1_x2.size(); i ++)
                res.push_back(make_pair(x1_x2[i].second, 0)); // Add the ground
                
            resSort(res, 0, res.size() - 1); // Quick Sort
            resSort_1(res); // Sort dots with same corrdiante
            resDel(res); // Delete dots on the same line
            return res;
        }
        
    private:
        void resSort_1(vector<pair<int, int> >& res) {
            for (int i = 0; i < res.size() - 1; i ++) {
                if (res[i].first == res[i + 1].first && res[i].second > res[i + 1].second) {
                    int x = res[i].second;
                    res[i].second = res[i + 1].second;
                    res[i + 1].second = x;
                }
            }
        }
        
        void resDel(vector<pair<int, int> >& res) {
            for (int i = 0; i < res.size() - 1; i ++) {
                if (res[i].second == res[i + 1].second) { // same height
                    res.erase(res.begin() + i + 1);
                    i --;
                }
                if (res[i].first == res[i + 1].first) { // same coordinate
                    if (res[i].second < res[i + 1].second)
                        res.erase(res.begin() + i  + 1);
                    else
                        res.erase(res.begin() + i);
                    i --;
                }
            }
        }
           
        void resSort(vector<pair<int, int> >& res, int start, int end) {
            if (start >= end)
                return;
            int first = start;
            int last = end;
            
            pair<int, int> key = res[first];
            while (first < last) {
                while (first < last && res[last].first >= key.first)
                    last --;
                res[first] = res[last];
                while (first < last && res[first].first <= key.first)
                    first ++;
                res[last] = res[first];
            } 
            res[first] = key;
            resSort(res, start, first - 1);
            resSort(res, first + 1, end);
        }
        
        void Add(const int x1, const int x2, vector<pair<int, int> >& x1_x2) {
            if (x1_x2.size() == 0)
                x1_x2.push_back(make_pair(x1, x2));
            for (int i = 0; i < x1_x2.size(); i ++) {
                if (x2 < x1_x2[i].first) { // all block non-overlap, to the left
                    x1_x2.insert(x1_x2.begin() + i, make_pair(x1, x2));
                    return;
                } else if (x1 < x1_x2[i].first && x2 >= x1_x2[i].first && x2 <= x1_x2[i].second) { // overlap on left part
                    x1_x2[i].first = x1;
                    return;
                } else if (x1 >= x1_x2[i].first && x2<= x1_x2[i].second) { // be concluded by the i'th block
                    return;
                } else if (x1 <= x1_x2[i].second && x2 > x1_x2[i].second) { // concluded the i'th block,or overlap on right part
                    int new_x1 = min(x1, x1_x2[i].first);
                    x1_x2.erase(x1_x2.begin() + i);
                    Add(new_x1, x2, x1_x2);
                    return;
                } else if (i == x1_x2.size() - 1){ // all block non-overlap, to the right
                    x1_x2.push_back(make_pair(x1, x2));
                }
                // continue;
            } 
        }
        
        static bool my_sort(pair<int, pair<int, int> >& l1, pair<int, pair<int, int> >& l2) {
            return (l1.first > l2.first);
        }
    };
    

Log in to reply
 

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