218 The Skyline Problem

https://leetcode.com/problems/the-skyline-problem/

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ].

The output is a list of "key points" (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as: [ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Notes:

• The number of buildings in any input list is guaranteed to be in the range [0, 10000].
• The input list is already sorted in ascending order by the left x position Li.
• The output list must be sorted by the x position.
• There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...]is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...].

Solution
Segment Tree

class Solution {
  struct segTreeNode {
    int lbd, ubd, height;
    segTreeNode* left, *right;
    segTreeNode(int l, int u, int h): lbd(l), ubd(u), height(h), left(NULL), right(NULL) {};
  };
  void insert(segTreeNode* root, int l, int u, int h) {
    if ( l >= u ) return;
    if ( h <= root->height ) return;
    if ( l == root->lbd and u == root->ubd and root->left == NULL and root->right == NULL) {
      root->height = h;
      return;
    }
    if ( root->left == NULL and root->right == NULL ) {
      int tmp;
      if ( l == root->lbd ) tmp = u;
      else tmp = l;
      root->left = new segTreeNode(root->lbd, tmp, root->height);
      root->right = new segTreeNode(tmp, root->ubd, root->height);
    }
    int divide = root->left->ubd;
    insert(root->left, l, min(divide, u), h);
    insert(root->right, max(divide,l), u, h);
  }

  vector<pair<int, int> > getInfo(segTreeNode* root) {
    vector<pair<int, int> > res;
    if ( root->left == NULL and root->right == NULL ) {
      res.push_back(pair<int, int> (root->lbd, root->height) );
      return res;
    }
    vector<pair<int, int> > left = getInfo(root->left);
    vector<pair<int, int> > right = getInfo(root->right);
    int l = left.size(), r = right.size();
    for ( int i = 0; i < r; i++ ) {
      if ( i == 0 and l != 0 and right[0].second == left[l-1].second ) continue;
      left.push_back(right[i]);
    }
    return left;
  }
  public:
    vector<pair<int, int> > getSkyline(vector<vector<int> >& buildings) {
      int n = buildings.size();
      vector<pair<int, int> > res;
      if ( n == 0 ) return res;
      int lbd = INT_MAX, ubd = INT_MIN;
      for ( int i = 0; i < n; i++ ) {
        lbd = min(lbd, buildings[i][0]);
        ubd = max(ubd, buildings[i][1]);
      }
      segTreeNode *root = new segTreeNode(lbd, ubd, 0);
      for ( int i = 0; i < n; i++ ) insert(root, buildings[i][0], buildings[i][1], buildings[i][2]);
      res = getInfo(root);
      res.push_back(pair<int, int>(ubd, 0));
      return res;
    }
};

自己比照着线段树定义想的解法。（中间bug无数） 每个节点保存左边界、右边界和高度。不断插入buildings[i]。这里的分情况讨论比较复杂，感觉是不是还可以更简化一点？

heap & hashmap solution

class Solution {
public:
    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
        int n = buildings.size();
        vector<pair<int, int>> res, ans;
        for ( int i = 0; i < n; i++ ) {
            res.push_back(pair<int, int>(buildings[i][0], buildings[i][2]));
            res.push_back(pair<int, int>(buildings[i][1], -buildings[i][2]));
        }
        sort(res.begin(), res.end());
        priority_queue<int> heap;
        unordered_map<int, int> map;
        heap.push(0);
        map[0] = 1;
        n = res.size();
        for ( int i = 0; i < n; i++ ) {
            int h = res[i].second;
            if ( h < 0 ) {
                map[-h] -= 1;
                if ( map[-h] == 0 )  map.erase(map.find(-h));
            }
            else {
                heap.push(h);
                if ( map.find(h) == map.end() ) map[h] = 1;
                else map[h] += 1;
            }
            while ( map.find(heap.top()) == map.end() ) heap.pop();
            res[i].second = heap.top();
            if ( i <= n-2 and res[i].first == res[i+1].first ) continue;
            if ( int(ans.size()) > 0 and res[i].second == ans[ans.size()-1].second ) continue;
            ans.push_back(res[i]);
        }
        return ans;
    }
};

一个非常巧妙的思路，一个点一个点处理，把每个点的坐标存在一个数组里，如果这个点是左边界，y值就取高度；如果是右边界，就取高度的相反数。对这些点按照x的值排序。

• 最终输出的点的横坐标一定是在这些横坐标中。
• 每个横坐标对应的纵坐标是当前最高的高度。
• 我们额外用一个heap和一个hashmap存当前有的高度，heap负责输出当前最大高度；hashmap负责即使删除遇到右边界的高度。 在处理细节上需要注意：
• 不是每个横坐标最终都需要保存，要看高度是否发生了变化；
• 每个横坐标可能对应多个纵坐标值，需要处理完所有横坐标之后再比较决定是否保存。 几个容易出错的corner case:

1. [[1, 2, 1], [1, 2, 2], [1, 2, 3]]
2. [[1, 2, 3], [2, 5, 3]]
3. [[1, 2, 3], [2, 5, 6]]