天际线问题

本题需要用到扫描线算法，不需要线段树（不需要区间查询）。

扫描线算法适合求由若干个矩形叠成的不规则图形的周长、面积问题。

本题需要输出所有横边的左端点，需要考虑一些边界情况。

首先需要找出所有竖边，求出所有竖边的顶点坐标存入一个 pair（pair 是双关键字排序），然后对这些坐标点进行排序。

排序时对于重合的两条竖边（横坐标一样，纵坐标不同）要分情况讨论：

假设两个点的坐标分别为 A(x, y)、B(x, z)。

  1. A 点是某个矩形的左端点，B 点是某个矩形的左端点。纵坐标高的排在前面。
  2. A 点是某个矩形的右端点，B 点是某个矩形的右端点。纵坐标低的排在前面。
  3. A 点是某个矩形的左端点，B 点是某个矩形的右端点。A 点排在前面。
  4. A 点是某个矩形的右端点，B 点是某个矩形的左端点。B 点排在前面。

总之，左端点重合，先大后小，右端点重合，先小后大，左右端点重合，先左后右。

在 pair 里面存左端点的时候，存负值。然后调用 sort 的时候就能自动实现上述排序规则。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
 public:
  vector<vector<int>> getSkyline(vector<vector<int>> &buildings) {
    vector<vector<int>> res;
    vector<pair<int, int>> points;
    multiset<int> heights;

    // 建立扫描线
    for (auto &b : buildings) {
      // 左端点，存负的高度
      points.push_back({b[0], -b[2]});
      // 右端点，存正的高度
      points.push_back({b[1], b[2]});
    }
    // 对扫描线排序，对于左端点相同的，高度高的排在前；对于右端点相同的，高度低的排在前面
    sort(points.begin(), points.end());
    heights.insert(0);
    for (auto &p : points) {
      int x = p.first, h = abs(p.second);
      if (p.second < 0) {  // 左端点
        if (h > *heights.rbegin()) {
          res.push_back({x, h});
        }
        heights.insert(h);
      } else {
        heights.erase(heights.find(h));
        if (h > *heights.rbegin()) {
          res.push_back({x, *heights.rbegin()});
        }
      }
    }
    return res;
  }
};