Smallest Range Covering Elements from K Lists

// C++
vector<int> smallestRange(vector<vector<int>>& nums) {
    using T = tuple<int,int,int>; // val, row, col
    priority_queue<T, vector<T>, greater<T>> minH;
    int curMax = INT_MIN;
    for (int i = 0; i < (int)nums.size(); i++) {
        minH.push({nums[i][0], i, 0});
        curMax = max(curMax, nums[i][0]);
    }
    vector<int> ans = {0, INT_MAX};
    while (!minH.empty()) {
        auto [val, row, col] = minH.top(); minH.pop();
        if (curMax - val < ans[1] - ans[0]) ans = {val, curMax};
        if (col + 1 >= (int)nums[row].size()) break;
        int nv = nums[row][col+1];
        curMax = max(curMax, nv);
        minH.push({nv, row, col+1});
    }
    return ans;
}

// Java
public int[] smallestRange(List<List<Integer>> nums) {
    PriorityQueue<int[]> minH = new PriorityQueue<>(Comparator.comparingInt(a -> nums.get(a[0]).get(a[1])));
    int curMax = Integer.MIN_VALUE;
    for (int i = 0; i < nums.size(); i++) {
        minH.offer(new int[]{i, 0});
        curMax = Math.max(curMax, nums.get(i).get(0));
    }
    int[] ans = {0, Integer.MAX_VALUE};
    while (!minH.isEmpty()) {
        int[] p = minH.poll();
        int val = nums.get(p[0]).get(p[1]);
        if (curMax - val < ans[1] - ans[0]) ans = new int[]{val, curMax};
        if (p[1]+1 >= nums.get(p[0]).size()) break;
        int nv = nums.get(p[0]).get(p[1]+1);
        curMax = Math.max(curMax, nv);
        minH.offer(new int[]{p[0], p[1]+1});
    }
    return ans;
}

# Python
import heapq

def smallestRange(nums):
    heap = [(lst[0], i, 0) for i, lst in enumerate(nums)]
    heapq.heapify(heap)
    cur_max = max(lst[0] for lst in nums)
    best = [float('-inf'), float('inf')]
    while heap:
        val, i, j = heapq.heappop(heap)
        if cur_max - val < best[1] - best[0]:
            best = [val, cur_max]
        if j + 1 >= len(nums[i]):
            break
        nv = nums[i][j + 1]
        cur_max = max(cur_max, nv)
        heapq.heappush(heap, (nv, i, j + 1))
    return best

// JavaScript
function smallestRange(nums) {
    const heap = nums.map((lst, i) => [lst[0], i, 0]);
    heap.sort((a, b) => a[0] - b[0]);
    let curMax = Math.max(...nums.map(l => l[0]));
    let best = [-Infinity, Infinity];
    while (heap.length === nums.length) {
        const [val, i, j] = heap.shift();
        if (curMax - val < best[1] - best[0]) best = [val, curMax];
        if (j + 1 >= nums[i].length) break;
        const nv = nums[i][j+1];
        curMax = Math.max(curMax, nv);
        let pos = heap.findIndex(x => x[0] >= nv);
        if (pos === -1) heap.push([nv, i, j+1]);
        else heap.splice(pos, 0, [nv, i, j+1]);
    }
    return best;
}