# A segment tree solution

• ``````class Solution {
public:
int tree[20000<<2] = {};
void update(int n, int l, int r, int left, int right, int value) {
if(l == left && r == right) {
tree[n] = max(tree[n], value);
}
else {
int m = (l+r)>>1;
if(right <= m) {
update(n<<1, l, m, left, right, value);
}
else if(left > m) {
update(n<<1|1, m+1, r, left, right, value);
}
else {
update(n<<1, l, m, left, m, value);
update(n<<1|1, m+1, r, m+1, right, value);
}
}
}
int query(int n, int l, int r, int index) {
if(l == r) {
return tree[n];
}
else {
int m = (l+r) >> 1;
int res = (index <= m ? query(n<<1, l, m, index) : query(n<<1|1, m+1, r, index));
return max(res, tree[n]);
}
}
vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
unordered_map<int, int> line;
unordered_map<int, int> rline;
int n = buildings.size();
set<int> l;
int top = -2;
int pre = -1;
for(int i = 0; i < n; i++) {
l.insert(buildings[i][0]);
l.insert(buildings[i][1]);
}
set<int>::iterator it;
for(it = l.begin(); it != l.end(); it++) {
if(pre != -1 && *it == pre+1) {
top++;
}
else {
top+=2;
}
line[*it] = top;
rline[top] = *it;
pre = *it;
}
for(int i = 0; i < n; i++) {
update(1, 0, top, line[buildings[i][0]], line[buildings[i][1]], buildings[i][2]);
}
vector<pair<int, int>> res;
int ph = 0;
for(int i = 0; i <= top; i++) {
int h = query(1, 0, top, i);
if(h != ph) {
res.push_back(make_pair(h > ph ? rline[i] : rline[i-1], h));
ph = h;
}
}
if(n > 0) {
res.push_back(make_pair((rline[top]), 0));
}
return res;
}
};``````

• Segment Tree by O(nlg(n)) time, 43 seconds in Java Version.

All buildings on X-axis construct at most buildings.length intervals, and this is the Segment Tree leaf node.
Before building this tree, we should also re-number these nodes.

For each tree node we maintain the max height of its range.

``````struct Node {
int startRange, endRange;
int maxHeight;
Node *pleft, *pright;
}
``````

Notes:

Here we use lazy propagation to update node. If at some node the range is exactly matched, update this node and don't update its child nodes.

Segment Tree Range Minimum Query

Lazy Propagation Segment Tree

``````class SegTree {
int[] segTree;  //从node = 1开始有效

public SegTree(int size) {
segTree = new int[size];
}

void update(int node, int startRange, int endRange, int left, int right, int value) {
if (left > right || right < startRange || left > endRange)
return;
//类似lazy propagation
if (startRange == left && endRange == right) {
segTree[node] = Math.max(segTree[node], value);
return;
}
int mid = (startRange + endRange) >> 1;
update(node << 1, startRange, mid, left, Math.min(mid, right), value);
update((node << 1) + 1, mid + 1, endRange, Math.max(mid + 1, left), right, value);
}

int query(int node, int startRange, int endRange, int index) {
if (startRange == endRange)
return segTree[node];
int mid = (startRange + endRange) >> 1;
int res = index <= mid ? query(node << 1, startRange, mid, index) : query((node << 1) + 1, mid + 1, endRange, index);
return Math.max(res, segTree[node]); //do this, because of lazy propagation
}
}

public class Solution {

public List<int[]> getSkyline(int[][] buildings) {
Set<Integer> ts = new TreeSet<>(); //sorted by ascending order
for (int i = 0; i < buildings.length; i++) {
}
//将X坐标区间到映射成1,2..连续值区间
Map<Integer, Integer> map = new HashMap<>(), rMap = new HashMap<>();
int k = 0;
for (Integer it : ts) {
map.put(it, k);
rMap.put(k++, it);
}
k = k - 1;
SegTree segTree = new SegTree((k + 1) << 4);
//build segTree
for (int i = 0; i < buildings.length; i++) {
segTree.update(1, 0, k, map.get(buildings[i][0]), map.get(buildings[i][4]) - 1, buildings[i][2]);
}
int preHeight = 0, height;
List<int[]> ret = new ArrayList<>();
for (int i = 0; i <= k; i++) {
height = segTree.query(1, 0, k, i);  //ith 区间max height
if (preHeight == height) continue; //连续区间相同高度 取第一个即可