632. Smallest Range Covering Elements from K Lists

multimap O(nlogk)
把heap换成multimap更直观，multimap里存的最小值和最大值就是当前可能的备选范围，不断减小最大值来得到新的最大值即可

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        multimap<int, int, greater<int>> m;
        int k = nums.size();
        for (int i = 0; i < k; ++i) {
            m.emplace(nums[i].back(), i);
            nums[i].pop_back();
        }
        vector<int> res{-100000, 100000};
        while (!m.empty()) {
            auto h = begin(m);
            auto l = rbegin(m);
            auto [hi, i] = *h;
            auto [lo, _] = *l;
            if (hi - lo <= res[1] - res[0]) {
                res = {lo, hi};
            }
            m.erase(h);
            if (nums[i].empty()) break;
            m.emplace(nums[i].back(), i);
            nums[i].pop_back();
        }
        return res;
    }
};

max heap O(nlogk) n是数的个数，k是数组个数，这里用最大堆是想让每个数组从后往前剔除元素，避免维护指针麻烦
题目解法和merge k sorted lists类似，上来先取每个数组的最大值放入堆，并维护一个全局最小值，然后不停从堆顶元素对应的数组取数并更新堆顶、全局最小值和最大值直到某个数组为空

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        using pii = pair<int, int>;
        priority_queue<pii, vector<pii>> q;
        int k = nums.size();
        int lo = INT_MAX, hi = INT_MIN;
        for (int i = 0; i < k; ++i) {
            lo = min(lo, nums[i].back());
            hi = max(hi, nums[i].back());
            q.emplace(nums[i].back(), i);
            nums[i].pop_back();
        }
        vector<int> res{lo, hi};
        while (!q.empty()) {
            auto [hi, i] = q.top(); q.pop();
            if (hi - lo <= res[1] - res[0]) { // 因为是有序的，所以不需要单独考虑差系统的情况，但是必须要用小于等于，因为是从大到小遍历的，所以后边有可能有差相同但是range开端更小的来overwrite结果
                res = {lo, hi};
            }
            if (nums[i].empty()) break;
            lo = min(lo, nums[i].back());
            q.emplace(nums[i].back(), i);
            nums[i].pop_back();
        }
        return res;
    }
};

greedy+sliding window O(nlogn + n) time O(n) space
题解

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        vector<pair<int, int>> ordered; // (number, group)
        for (int k = 0; k < nums.size(); ++k) {
            for (int x : nums[k]) {
                ordered.emplace_back(x, k);
            }
        }
        sort(ordered.begin(), ordered.end());
        int i = 0, k = size(nums);
        vector<int> res{-100000, 100000};
        unordered_map<int, int> count;
        for (int l = 0, r = 0; r < ordered.size(); ++r) {
            ++count[ordered[r].second];
            if (size(count) == k) {
                while (count[ordered[l].second] > 1) {
                    --count[ordered[l++].second];
                }
                if (ordered[r].first - ordered[l].first < res[1] - res[0]) {
                    res = {ordered[l].first, ordered[r].first};
                }
            }
        }

        return res;
    }
};