# 40ms c++ solution with segment tree

• 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;
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);
}
}
}

vector<pair<int, int>> getTall(Node* root)
{
vector<pair<int, int>> res;
int pre = 0;
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);
}
};``````

• why "point.first--" ?

• 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.

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