LeetCode-218 The Skyline Problem

Description

如图，求上升沿和下降沿转折处的坐标

Constraints

要求时间复杂度\(O(nlogn)\)，其中\(n\)为输入的建筑物个数

Solution

每个区间拆成2条纵线，按坐标\(x\)排序。然后用平衡树维护坐标\(y\)

Code

class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        // tuple: {x, h}
        vector<tuple<int, int>> lines;
        // NOTE1: sort the left-hand side first.
        for(auto &b : buildings) {
            lines.emplace_back(b[0], -b[2]);
            lines.emplace_back(b[1], +b[2]);
        }
        ranges::sort(lines);
        vector<vector<int>> ans;
        // NOTE2: {0} for --end.
        multiset<int> ms {0};
        int last = 0;
        for(auto [x, h] : lines) {
            h < 0 ? ms.emplace(-h) : ms.erase(ms.find(h));
            if(auto mx = *--ms.end(); last != mx) {
                ans.push_back({x, mx});
                last = mx;
            }
        }
        return ans;
    }
};

Link

LeetCode-218 The Skyline Problem