218. The Skyline Problem

class Solution { public: vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) { vector<pair<int, int>> height, skyline; for(auto b : buildings){ height.push_back(make_pair(b[0], -b[2])); height.push_back(make_pair(b[1], b[2])); } sort(height.begin(), height.end()); multiset<int> m; m.insert(0);//不太懂为什么这里要insert int start=0,cur=0; for(auto h : height){ if(h.second<0) m.insert(-h.second); else m.erase(m.find(h.second)); cur = *m.rbegin(); if(start != cur){ skyline.push_back(make_pair(h.first, cur)); start=cur; } } return skyline; } };

参考看这一篇https://briangordon.github.io/2014/08/the-skyline-problem.html

首先，对于这个问题来说，应当使用扫描线的思想，从左到右判断每个横坐标最高的高度值。但是对于矩形来说，没有必要判断每个横坐标，只需要判断每个矩形的边界其实就可以确定边界线的形状了。

因此先将每个矩形的两个边界节点及高度存储到map中, sort函数默认排pair的时候，先看first再看second。

然后从左到右遍历每个跳跃点，当一个矩形的左边界出现时，将它的高度插入堆中，当右边界出现时，将它的高度移除。对每个跳跃点来说，当前的高度值应该是堆中的最大值。

start代表当前的最大值，cur代表更新后当前的最大值，如果start！=cur的话证明最大值有更新，应当加入skyline中。