forked from MaskRay/LeetCode
-
Notifications
You must be signed in to change notification settings - Fork 1
/
the-skyline-problem.cc
61 lines (59 loc) · 1.44 KB
/
the-skyline-problem.cc
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// The Skyline Problem
class Solution {
public:
vector<pair<int, int>> getSkyline(vector<vector<int>>& a) {
int n = a.size(), xx = -1, x, yy = 0, y = 0;
priority_queue<pair<int, int>> pq; // order by first, second is insignificant
vector<pair<int, int>> 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<pair<int, int>> getSkyline(vector<vector<int>>& a) {
vector<pair<int, int>> 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<int> h;
vector<pair<int, int>> 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;
}
};