218. 天际线问题

class Solution {
public:
    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
      
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> leftx;
        for (int i = 0; i < buildings.size(); i++)
        {
            vector<int> b = buildings[i];
            leftx.push(make_pair(b[0], i));
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> rightx;
        for (int i = 0; i < buildings.size(); i++)
        {
            vector<int> b = buildings[i];
            rightx.push(make_pair(b[1], i));
        }

        map<int, int> h;

        int lasth = 0;
        int x = 0;

        vector<pair<int, int>> ret;

        while (!leftx.empty() || !rightx.empty())
        {
            int next = 0;
            if (!leftx.empty() && leftx.top().first <= rightx.top().first)
            {
                next = leftx.top().first;
            }
            else
            {
                next = rightx.top().first;
            }

            while (!leftx.empty() && leftx.top().first == next)
            {
                x = leftx.top().first;

                int index = leftx.top().second;
                leftx.pop();

                vector<int> b = buildings[index];
                h[index] = b[2];
            }

            while (!rightx.empty() && rightx.top().first == next)
            {
                x = rightx.top().first;
                int index = rightx.top().second;
                rightx.pop();

                h.erase(index);
            }

            int curh = 0;
            if (!h.empty())
            {
                int max = -1;
                for (map<int, int>::iterator it = h.begin(); it!=h.end();it++)
                {
                    if (it->second > max)
                    {
                        max = it->second;
                    }
                }
                curh = max;
            }

            if (curh != lasth)
            {
                lasth = curh;
                ret.push_back(make_pair(x, curh));
            }
        }

        return ret;
    }
};