Clean C++ priority_queue solution using iterators


  • 8
    A

    Yes. The idea is just similar to Merge K Sorted List. Keep a priority queue of iterators/pointers which points to the current head of a row.

    class Solution {
    public:
        vector<int> smallestRange(vector<vector<int>>& nums) {
            typedef vector<int>::iterator vi;
            
            struct comp {
                bool operator()(pair<vi, vi> p1, pair<vi, vi> p2) {
                    return *p1.first > *p2.first;
                }
            };
            
            int lo = INT_MAX, hi = INT_MIN;
            priority_queue<pair<vi, vi>, vector<pair<vi, vi>>, comp> pq;
            for (auto &row : nums) {
                lo = min(lo, row[0]);
                hi = max(hi, row[0]);
                pq.push({row.begin(), row.end()});
            }
            
            vector<int> ans = {lo, hi};
            while (true) {
                auto p = pq.top();
                pq.pop();
                ++p.first;
                if (p.first == p.second)
                    break;
                pq.push(p);
                
                lo = *pq.top().first;
                hi = max(hi, *p.first);
                if (hi - lo < ans[1] - ans[0])
                    ans = {lo, hi};
            }
            return ans;
        }
    };
    

  • 0

    @Aeonaxx
    The method of using iterators is cool!


  • 0
    A
    This post is deleted!

Log in to reply
 

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