632

class Solution {
public:
    typedef vector<int>::iterator vi;
    struct compare{
        bool operator()(const pair<vi, vi>& a, const pair<vi, vi>& b){
            return *(a.first) > *(b.first);
        }
    };

    vector<int> smallestRange(vector<vector<int>>& nums) {
        priority_queue<pair<vi, vi>, vector<pair<vi, vi>>, compare> pq;

        int low = INT_MAX, high=INT_MIN;
        for(auto &row : nums){
            low = min(low, row[0]);
            high = max(high, row[0]);
            pq.push({row.begin(), row.end()});
        }
        vector<int> ans = {low, high};

        while(true){
            auto ptr = pq.top();
            pq.pop();
            ++ptr.first;
            if(ptr.first == ptr.second) break;
            pq.push(ptr);
            auto top = pq.top();
            low = *(top.first);
            high = max(high, *(ptr.first));

            if(high-low < ans[1]-ans[0]){
                ans[1] = high;
                ans[0] = low;
            }
        }
        return ans;
    }
};