// The Skyline Problem class Solution { public: vector> getSkyline(vector>& a) { int n = a.size(), xx = -1, x, yy = 0, y = 0; priority_queue> pq; // order by first, second is insignificant vector> r; for (int i = 0; i < n || pq.size(); ) { if (pq.empty() || i < n && a[i][0] < pq.top().second) { x = a[i][0]; pq.emplace(a[i][2], a[i][1]); i++; } else { x = pq.top().second; while (pq.size() && pq.top().second <= x) pq.pop(); } if (x != xx && y != yy) { r.emplace_back(xx, y); yy = y; } xx = x; y = pq.empty() ? 0 : pq.top().first; } if (y != yy) r.emplace_back(xx, y); return r; } }; /// class Solution { public: vector> getSkyline(vector>& a) { vector> ev; for (auto &e: a) { ev.emplace_back(e[0], e[2]); ev.emplace_back(e[1], - e[2]); } sort(ev.begin(), ev.end()); int x = -1, y = 0, yy = 0; multiset h; vector> r; for (auto e: ev) { if (e.second > 0) h.insert(e.second); else h.erase(h.find(- e.second)); if (e.first != x && yy != y) { r.emplace_back(x, y); yy = y; } x = e.first; y = h.empty() ? 0 : *h.rbegin(); } if (yy != y) r.emplace_back(x, y); return r; } };