c++ O(nlogn) solution using priority queue and map


  • 0

    The solution is based on the following link:
    https://www.youtube.com/watch?v=GSBLe8cKu0s

    struct MyPair{
        int x, h, i;
        MyPair(int a, int b, int c): x(a), h(b), i(c) {}
    };
    bool operator>(MyPair p1, MyPair p2) {
        return p1.x == p2.x ? p1.h * p1.i < p2.h * p2.i : p1.x > p2.x;
    }
    class Solution {
    public:
        vector<pair<int, int>> getSkyline(vector<vector<int>>& b) {
            priority_queue<MyPair, vector<MyPair>, greater<MyPair>> p;
            map<int, int> s;
            vector<pair<int, int>> res;
            for (vector<int> v : b) {
                p.push(MyPair(v[0], v[2], 1));
                p.push(MyPair(v[1], v[2], -1));
                
            }
            s[0] = 1;
            while (p.size()) {
                MyPair m = p.top();
                p.pop();
                int prev_max = s.rbegin()->first;
                if (m.i == 1) {
                    s[m.h]++;
                    if (prev_max < s.rbegin()->first) {
                        res.push_back(make_pair(m.x, m.h));
                    }
                } else {
                    s[m.h]--;
                    if (s[m.h] == 0) s.erase(m.h);
                    int cur_max = s.rbegin()->first;
                    if (cur_max != prev_max) {
                        res.push_back(make_pair(m.x, cur_max));
                    }
                }
            }
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.