C++ priority_queue with iterator


  • 0
    C
    class Solution {
    public:
        vector<int> smallestRange(vector<vector<int>>& nums) {
            int left = INT_MAX, right = INT_MIN;
            // construct a min-heap store k nums
            using pair_t = std::pair<vector<int>::iterator, int>;
            auto cmp = [](const pair_t l, const pair_t r){return *(l.first) > *(r.first);};
            priority_queue<pair_t, vector<pair_t>, decltype(cmp)> q(cmp);
            for (int i=0; i<nums.size(); ++i){
                auto it = nums[i].begin();
                left = min(left, *it);
                right = max(right, *it);
                q.push({ it, i});
            }
    
            // slide against all nums
            vector<int> res = {left, right};
            int min_gap = right - left;
            auto prev = q.top();
            while(next(prev.first) != nums[prev.second].end()){
                q.pop();
                q.push({ ++(prev.first), prev.second});
                left = *q.top().first;
                right = max(right, *prev.first);
                prev = q.top();
                if (min_gap > (right-left)){
                    min_gap = right - left;
                    res = {left, right};
                }
            }
    
            return res;
        }
    };
    

Log in to reply
 

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