Smallest Range Covering Elements from K Lists

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> pq;
        int curMax = INT_MIN;
        for (int i = 0; i < (int)nums.size(); ++i) {
            pq.emplace(nums[i][0], i, 0);
            curMax = max(curMax, nums[i][0]);
        }
        int rangeLo = -1e5, rangeHi = 1e5;
        while (true) {
            auto [v, li, ii] = pq.top(); pq.pop();
            if (curMax - v < rangeHi - rangeLo) {
                rangeLo = v;
                rangeHi = curMax;
            }
            if (ii + 1 == (int)nums[li].size()) break;
            int nxt = nums[li][ii + 1];
            curMax = max(curMax, nxt);
            pq.emplace(nxt, li, ii + 1);
        }
        return {rangeLo, rangeHi};
    }
};

import (
    "container/heap"
    "math"
)

type item struct{ v, li, ii int }
type itemHeap []item

func (h itemHeap) Len() int            { return len(h) }
func (h itemHeap) Less(i, j int) bool  { return h[i].v < h[j].v }
func (h itemHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *itemHeap) Push(x interface{}) { *h = append(*h, x.(item)) }
func (h *itemHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func smallestRange(nums [][]int) []int {
    pq := &itemHeap{}
    heap.Init(pq)
    curMax := math.MinInt32
    for i := 0; i < len(nums); i++ {
        heap.Push(pq, item{nums[i][0], i, 0})
        if nums[i][0] > curMax {
            curMax = nums[i][0]
        }
    }
    rangeLo, rangeHi := -100000, 100000
    for {
        top := heap.Pop(pq).(item)
        if curMax-top.v < rangeHi-rangeLo {
            rangeLo = top.v
            rangeHi = curMax
        }
        if top.ii+1 == len(nums[top.li]) {
            break
        }
        nxt := nums[top.li][top.ii+1]
        if nxt > curMax {
            curMax = nxt
        }
        heap.Push(pq, item{nxt, top.li, top.ii + 1})
    }
    return []int{rangeLo, rangeHi}
}

import heapq
from typing import List

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        pq: List = []
        cur_max = float('-inf')
        for i, row in enumerate(nums):
            heapq.heappush(pq, (row[0], i, 0))
            if row[0] > cur_max:
                cur_max = row[0]
        range_lo, range_hi = -10**5, 10**5
        while True:
            v, li, ii = heapq.heappop(pq)
            if cur_max - v < range_hi - range_lo:
                range_lo = v
                range_hi = cur_max
            if ii + 1 == len(nums[li]):
                break
            nxt = nums[li][ii + 1]
            if nxt > cur_max:
                cur_max = nxt
            heapq.heappush(pq, (nxt, li, ii + 1))
        return [range_lo, range_hi]

class MinHeap {
    constructor() { this.h = []; }
    size() { return this.h.length; }
    push(v) {
        this.h.push(v);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p][0] <= this.h[i][0]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop() {
        const top = this.h[0];
        const last = this.h.pop();
        if (this.h.length) {
            this.h[0] = last;
            let i = 0;
            const n = this.h.length;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let s = i;
                if (l < n && this.h[l][0] < this.h[s][0]) s = l;
                if (r < n && this.h[r][0] < this.h[s][0]) s = r;
                if (s === i) break;
                [this.h[i], this.h[s]] = [this.h[s], this.h[i]];
                i = s;
            }
        }
        return top;
    }
}

function smallestRange(nums) {
    const pq = new MinHeap();
    let curMax = -Infinity;
    for (let i = 0; i < nums.length; i++) {
        pq.push([nums[i][0], i, 0]);
        if (nums[i][0] > curMax) curMax = nums[i][0];
    }
    let rangeLo = -1e5, rangeHi = 1e5;
    while (true) {
        const [v, li, ii] = pq.pop();
        if (curMax - v < rangeHi - rangeLo) {
            rangeLo = v;
            rangeHi = curMax;
        }
        if (ii + 1 === nums[li].length) break;
        const nxt = nums[li][ii + 1];
        if (nxt > curMax) curMax = nxt;
        pq.push([nxt, li, ii + 1]);
    }
    return [rangeLo, rangeHi];
}

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        int curMax = Integer.MIN_VALUE;
        for (int i = 0; i < nums.size(); i++) {
            int v = nums.get(i).get(0);
            pq.offer(new int[]{v, i, 0});
            if (v > curMax) curMax = v;
        }
        int rangeLo = -100000, rangeHi = 100000;
        while (true) {
            int[] top = pq.poll();
            int v = top[0], li = top[1], ii = top[2];
            if (curMax - v < rangeHi - rangeLo) {
                rangeLo = v;
                rangeHi = curMax;
            }
            if (ii + 1 == nums.get(li).size()) break;
            int nxt = nums.get(li).get(ii + 1);
            if (nxt > curMax) curMax = nxt;
            pq.offer(new int[]{nxt, li, ii + 1});
        }
        return new int[]{rangeLo, rangeHi};
    }
}

class MinHeap {
    private h: [number, number, number][] = [];
    size(): number { return this.h.length; }
    push(v: [number, number, number]): void {
        this.h.push(v);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p][0] <= this.h[i][0]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop(): [number, number, number] {
        const top = this.h[0];
        const last = this.h.pop()!;
        if (this.h.length) {
            this.h[0] = last;
            let i = 0;
            const n = this.h.length;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let s = i;
                if (l < n && this.h[l][0] < this.h[s][0]) s = l;
                if (r < n && this.h[r][0] < this.h[s][0]) s = r;
                if (s === i) break;
                [this.h[i], this.h[s]] = [this.h[s], this.h[i]];
                i = s;
            }
        }
        return top;
    }
}

function smallestRange(nums: number[][]): number[] {
    const pq = new MinHeap();
    let curMax = -Infinity;
    for (let i = 0; i < nums.length; i++) {
        pq.push([nums[i][0], i, 0]);
        if (nums[i][0] > curMax) curMax = nums[i][0];
    }
    let rangeLo = -1e5, rangeHi = 1e5;
    while (true) {
        const [v, li, ii] = pq.pop();
        if (curMax - v < rangeHi - rangeLo) {
            rangeLo = v;
            rangeHi = curMax;
        }
        if (ii + 1 === nums[li].length) break;
        const nxt = nums[li][ii + 1];
        if (nxt > curMax) curMax = nxt;
        pq.push([nxt, li, ii + 1]);
    }
    return [rangeLo, rangeHi];
}