26 ms C++ submission. Scan-lines with three stages


  • 0
    H
    class Solution {
    public:
        vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
            if (buildings.size() == 0) {
                return vector<pair<int, int>>();
            }
            // Stage 1: produce scan lines
            vector<pair<int, int>> lines;   lines.reserve(buildings.size() * 2);
            for (int i = 0; i < buildings.size(); ++i) {
                lines.push_back(make_pair(buildings[i][0], i));
                lines.push_back(make_pair(buildings[i][1], i));
            }
            sort(lines.begin(), lines.end());
            
            // Stage 2: Get the y for each scan line. 
            // There might be some many x with same y in the array
            vector<pair<int, int>> sl;
            priority_queue<pair<int, int>> heights;
            for (int i = 0; i < lines.size(); ) {
                int x = lines[i].first;
                for (; i < lines.size() && (i == 0 || lines[i].first == x); ++i) {
                    heights.push(make_pair(buildings[lines[i].second][2], lines[i].second));
                }
                while (!heights.empty() && buildings[heights.top().second][1] <= x) {
                    heights.pop();
                }
                sl.push_back(make_pair(x, !heights.empty() ? heights.top().first : 0));
            }
            
            // Stage 3: remove the items that has same y as previous item
            int inserti = 0;
            for (int i = 1; i < sl.size(); ++i) {
                if (sl[i].second != sl[inserti].second) {
                    sl[++inserti] = sl[i];
                }
            }
            sl.resize(inserti + 1);
            return sl;
        }
    };
    

    This is not the fastest one, but I think the algorithm is easy to understand.


Log in to reply
 

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