40ms c++ solution with segment tree


  • 0
    W

    I use a segment tree to solve this problem.
    Notes, only the leaf node indicates the truly segment. And factors a and b indicate the beginning and ending of a segment.

    class Solution {
    public:
        class Node
        {
        public:
            int tall;     // the minimun tall of this seg
            long long a;  // beginning of this seg
            long long b;  // ending of this seg
            Node* left, *right;
            Node()
            {
                tall = 0;
                a = b = 0;
                left = right = NULL;
            }
        };
        
        void buildTree(Node* root, int &val, long long aa, long long bb)
        {
            if(val < root->tall)
                return;
            if(root->a == aa && root->b == bb && root->left == NULL && root->right == NULL)
                root->tall = max(root->tall, val);
            else
            {
                long long mid = (root->a + root->b) / 2;
                if(root->left == NULL)
                {
                    root->left = new Node;
                    root->right = new Node;
                    root->left->a = root->a;
                    root->left->b = mid;
                    root->right->a = mid + 1;
                    root->right->b = root->b;
                    root->left->tall = root->right->tall = root->tall;
                }
                if(bb <= mid)
                {
                    buildTree(root->left, val, aa, bb);
                }
                else if(aa > mid)
                {
                    buildTree(root->right, val, aa, bb);
                }
                else
                {
                    buildTree(root->left, val, aa, mid);
                    buildTree(root->right, val, mid + 1, bb);
                }
                root->tall = min(root->left->tall, root->right->tall);
            }
        }
        
        void addLeaf(Node* root, vector<pair<int, int>> &res, int& pre)
        {
            if(root == NULL)
                return;
            addLeaf(root->left, res, pre);
            if(root->left == NULL && root->right == NULL)
            {
                if(root->tall != pre)
                {
                    pair<int, int> point(root->a, root->tall);
                    if(root->tall < pre)
                    point.first--;
                    pre = root->tall;
                    res.push_back(point);
                }
            }
            addLeaf(root->right, res, pre);
        }
        
        vector<pair<int, int>> getTall(Node* root)
        {
            vector<pair<int, int>> res;
            int pre = 0;
            addLeaf(root, res, pre);
            if(res.size() != 0 && res.back().second != 0)
                res.push_back(pair<int, int> (INT_MAX, 0));
            return res;
        }
        vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
            Node *root = new Node;
            root->a = 0;
            root->b = INT_MAX;
            for(vector<int> building : buildings)
                buildTree(root, building[2], building[0], building[1]);
            return getTall(root);
        }
    };

  • 0
    M

    why "point.first--" ?


  • 0
    W

    In my tree, for instance, range from 0 - 4, will be divided to two ranges: 0 - 2 and 3 - 4.
    (1) insert [3, 4, 1]: of course, the right->tall = 1, and skyline are [3, 1] [4, 0]
    (2) insert [0, 2, 1]: the left->tall = 1 but the skyline are [0,1] [2, 1], not [0,1] [3,1]
    And I only check every left-value(Node::a) for each segment. So if Node::tall is smaller than pre, it means case(2) is met. The skyline should be the left x of point.first.


Log in to reply
 

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