Description

Submission

class Solution {
    typedef long long ll;
    typedef array<ll, 3> AL3;
public:
    vector<vector<long long>> splitPainting(vector<vector<int>>& segments) {
        priority_queue<AL3, vector<AL3>, greater<>> pq;     // start, end, color
        
        for(auto segment: segments) {
            pq.push({segment[0], segment[1], segment[2]});
        }
        
        vector<vector<ll>> rets;
        set<AL3> candidates; // end matters the most
        ll sumColor = 0;
        int curStart = 0;
        
        while(!pq.empty() || !candidates.empty()) {
            
            if(!pq.empty() && pq.top()[0] < curStart) {
                for(auto [e, s, c]: candidates) {
                    pq.push({s, e, c});
                }
                sumColor = 0;
                candidates = {};
            }
            
            if(candidates.empty()) {
                curStart = pq.top()[0];
            }
            
            while(!pq.empty() && pq.top()[0] == curStart) {
                auto [s, e, c] = pq.top();
                candidates.insert({e, s, c});
                sumColor += c;
                pq.pop();
            } 
            
            ll end = candidates.begin()->at(0);
            
            if(!pq.empty()) end = min(end, pq.top()[0]);
            
            int newLen = end - curStart;
            
            rets.push_back({curStart, end, sumColor});
            curStart += newLen;
            
            while(!candidates.empty() && candidates.begin()->at(0) == end) {
                sumColor -= candidates.begin()->at(2);
                candidates.erase(candidates.begin());
            }
        }
        
        return rets;
    }
};