LeetCode 218. The Skyline Problem

Posted on Edited on In 
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
class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) -> bool { return a.second < b.second; };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> q(cmp);
        vector<int> boundaries;
        for (auto& building : buildings) {
            boundaries.emplace_back(building[0]);
            boundaries.emplace_back(building[1]);
        }
        sort(boundaries.begin(), boundaries.end());
        vector<vector<int>> ans;
        int n = buildings.size(), i = 0;
        for (auto& b : boundaries) {
            while (i < n && buildings[i][0] <= b) {
                q.emplace(buildings[i][1], buildings[i][2]);
                ++i;
            }
            while (!q.empty() && q.top().first <= b)
                q.pop();
            int maxn = q.empty() ? 0 : q.top().second;
            if (ans.empty() || maxn != ans.back()[1])
                ans.push_back({b, maxn});
        }
        return ans;
    }
};
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
class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        int n = buildings.length, i = 0, prevh = 0;
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        int[] boundaries = new int[n * 2];
        for (int[] b : buildings) {
            boundaries[i++] = b[0];
            boundaries[i++] = b[1];
        }
        Arrays.sort(boundaries);
        ArrayList<List<Integer>> ans = new ArrayList<>();
        i = 0;
        for (int b : boundaries) {
            while (i < n && buildings[i][0] <= b) {
                q.offer(new int[]{buildings[i][1], buildings[i][2]});
                ++i;
            }
            while (!q.isEmpty() && q.peek()[0] <= b)
                q.poll();
            int h = q.isEmpty() ? 0 : q.peek()[1];
            if (ans.isEmpty() || h != prevh)
                ans.add(List.of(b, prevh = h));
        }
        return ans;
    }
}