2015. Average Height of Buildings in Each Segment

A perfectly straight street is represented by a number line. The street has building(s) on it and is represented by a 2D integer array buildings, where buildings[i] = [starti, endi, heighti]. This means that there is a building with heighti in the half-closed segment [starti, endi).

You want to describe the heights of the buildings on the street with the minimum number of non-overlapping segments. The street can be represented by the 2D integer array street where street[j] = [leftj, rightj, averagej] describes a half-closed segment [leftj, rightj) of the road where the average heights of the buildings in the segment is averagej.

• For example, if buildings = [[1,5,2],[3,10,4]], the street could be represented by street = [[1,3,2],[3,5,3],[5,10,4]] because:

• From 1 to 3, there is only the first building with an average height of 2 / 1 = 2.
• From 3 to 5, both the first and the second building are there with an average height of (2+4) / 2 = 3.
• From 5 to 10, there is only the second building with an average height of 4 / 1 = 4.

Given buildings, return the 2D integer array street as described above (excluding any areas of the street where there are no buldings). You may return the array in any order.

The average of n elements is the sum of the n elements divided (integer division) by n.

A half-closed segment [a, b) is the section of the number line between points a and b including point a and not including point b.

class Solution {
    void compress(vector<vector<int>>& res) {
        while(res.size() >= 2 and res[res.size() - 1][2] == res[res.size() - 2][2] and res[res.size() - 1][0] == res[res.size() - 2][1]) {
            res[res.size() - 2][1] = res[res.size() - 1][1];
            res.pop_back();
        }
    }
    
    int erase(priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>& pq, int target) {
        int res = 0;
        while(!pq.empty() and pq.top().first == target) {
                res += pq.top().second;
                pq.pop();
        }
        return res;
    }
    
    int insert(vector<vector<int>>& A, priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>& pq, int target) {
        int res = 0;
        while(!A.empty() and A.back()[0] == target) {
            res += A.back()[2];
            pq.push({A.back()[1], A.back()[2]});
            A.pop_back();
        }
        return res;
    }
public:
    vector<vector<int>> averageHeightOfBuildings(vector<vector<int>>& A) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        int sum = 0, n = A.size(), last = 0, i = 0;
        vector<vector<int>> res;
        sort(rbegin(A), rend(A));
        while(!A.empty()) {
            int start = A.back()[0];
            if(!pq.empty()) start = min(start, pq.top().first);
            if(sum) res.push_back({last, start, (int)(sum / pq.size())});
            sum -= erase(pq,start);
            sum += insert(A,pq,start);
            last = start;
            compress(res);
        }
        
        while(!pq.empty()) {
            auto [e, _] = pq.top();
            res.push_back({last, e, (int)(sum / pq.size())});
            
            sum -= erase(pq,e);
            
            compress(res);
            last = e;
        }
        return res;
    }
};