Clean C++ Code using SegmentTree and Discretization


  • 0
    D
    #define lson l, m, rt << 1
    #define rson m + 1, r, rt << 1 | 1
    class Solution {
    public:
        vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
            if(buildings.size() < 1) 
                return vector<pair<int, int>>();
            
            set<int> s;
            
            for (const auto & building : buildings)
            {
                s.insert(building[0]);
                s.insert(building[1]);
                s.insert(building[1] - 1);
            }
            
            unordered_map<int,int> idxs;
            vector<int> nums(s.size());
            int cnt = 0;
            for(int num : s) {
                nums[cnt] = num;
                idxs[num] = cnt++;
            }
        
            vector<int> heights(cnt << 2);
            build(heights, 0, cnt - 1, 1);
            
            for (const auto & building : buildings)
            {
                int L = idxs[building[0]], R = idxs[building[1] - 1], h = building[2];
                update(heights, L, R, h, 0, cnt - 1, 1);
            }
            
            vector<pair<int,int>> ret;
            for(int i = 0,last = -1; i < cnt; i++)
            {
                int tmp = query(heights, i, 0, cnt- 1, 1);
                if(tmp != last)
                    ret.push_back(pair<int,int>(nums[i], tmp));
                last = tmp;
            }
            return ret;
        }
        
        void build(vector<int>& heights, int l, int r, int rt) {
            if (l == r) {
                heights[rt] = 0;
                return;
            }
            int m = (l + r) >> 1;
            build(heights, lson);
            build(heights, rson);
        }
        
        void pushDown(vector<int>& heights, int rt) {
            if (heights[rt] != 0) {
                heights[rt << 1] = max(heights[rt], heights[rt << 1]);
                heights[rt << 1 | 1] = max(heights[rt], heights[rt << 1 | 1]);
                heights[rt] = 0;
            }
        }
        
        void update(vector<int>& heights, int L, int R, int h, int l, int r, int rt) {
            if (L <= l && r <= R) {
                heights[rt] = max(heights[rt], h);
                return;
            }
            pushDown(heights, rt);
            int m = (l + r) >> 1;
            if (L <= m) update(heights, L, R, h, lson);
            if (R > m) update(heights, L, R, h, rson);
        }
        
        int query(vector<int>& heights, int idx, int l, int r, int rt) {
            if (l == r) {
                return heights[rt];
            }
            pushDown(heights, rt);
            int m = (l + r) >> 1;
            if (idx <= m) return query(heights, idx, lson);
            else return query(heights, idx, rson);
        }
    };
    

Log in to reply
 

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