LeetCode218 天际线问题

链接： https://leetcode-cn.com/problems/merge-k-sorted-lists/

题面

给定建筑物的起止位置和高度，返回建筑物轮廓（天际线）的拐点。

解法

这是一道hard难度的题目 需要考虑用优先队列来求解
存储每个建筑物的高度右端点，以高度作为第一关键字，右端点为第二关键字
从而获取到目前会拔高天际线、且阻碍前一个建筑物的右端点的下一个建筑物
有很多细节 不太好写 参考了示例程序写出来的

代码

class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        priority_queue<pair<int, int>> pq;
        vector<vector<int>> ans;
        int cur_x = 0, cur_h = 0;
        int ind = 0, len = buildings.size();
        while(ind < len || pq.size()) {
            if(pq.empty() || ind < len && buildings[ind][0] <= pq.top().second) {
                // 如果下一个building的左端点小于当前最高建筑物的右端点
                cur_x = buildings[ind][0]; // 更新当前的横坐标
                while(ind < len && cur_x == buildings[ind][0]) {
                    pq.push({buildings[ind][2], buildings[ind][1]});
                    ind++;
                }
            }
            else {
                // 出现下一建筑的左端点大于当前最高建筑物的右端点时
                cur_x = pq.top().second; // 更新当前的横坐标
                while(pq.size() && pq.top().second <= cur_x) {
                    pq.pop();
                }
            }
            // 如果pq为空 则更新为0
            cur_h = (pq.size()) ? pq.top().first : 0; // 更新当前的最大高度
            
            if (ans.empty() || ans.back()[1] != cur_h) { // 如果高度发生变化（升高或者降低）
                ans.push_back({cur_x, cur_h});
            }
        }
        return ans;
    }
};