632. 最小区间

func smallestRange(nums [][]int) []int

// 记录每个列表当前尝试元素的索引
var pos []int

func smallestRange(nums [][]int) []int {
	size := len(nums)
	pos = make([]int, size)

	h := &Heap{s: make([]Item, 0, size)}
	curMax := math.MinInt32
	// 先处理每个列表首元素
	for i, v := range nums {
		heap.Push(h, Item{val: v[0], listIndex: i})
		curMax = max(curMax, v[0])
	}
	lo, hi, minAbs := math.MinInt32, math.MaxInt32, math.MaxInt32
	for {
		peek := h.s[0] // 堆顶
		abs := curMax - peek.val
		if abs < minAbs {
			minAbs = abs
			lo = peek.val
			hi = curMax
		}
		index := peek.listIndex
		curPos := pos[index] + 1
		if curPos == len(nums[index]) {
			break
		}
		pos[index] = curPos
		curNum := nums[index][curPos]
		h.s[0].val = curNum
		heap.Fix(h, 0)
		curMax = max(curMax, curNum)
	}
	return []int{lo, hi}
}

type Item struct {
	val, listIndex int // 记录每个数字及其所在列表的索引
}

type Heap struct {
	s []Item
}

func (h *Heap) Len() int           { return len(h.s) }
func (h *Heap) Swap(i, j int)      { h.s[i], h.s[j] = h.s[j], h.s[i] }
func (h *Heap) Less(i, j int) bool { return h.s[i].val < h.s[j].val }
func (h *Heap) Push(x interface{}) { h.s = append(h.s, x.(Item)) }
func (h *Heap) Pop() interface{} {
	x := h.s[len(h.s)-1]
	h.s = h.s[:len(h.s)-1]
	return x
}

func smallestRange1(nums [][]int) []int {
	size := len(nums)
	indices := map[int][]int{}                 // 记录每个数字所在列表的索引
	xMin, xMax := math.MaxInt32, math.MinInt32 // 分别记录所有数字中的最小和最大元素
	for i, v := range nums {
		for _, x := range v {
			indices[x] = append(indices[x], i)
			xMin = min(xMin, x)
			xMax = max(xMax, x)
		}
	}
	freq := make([]int, size)
	inside := 0
	start, end := xMin, xMax
	for left, right := xMin, xMin; right < xMax; right++ {
		if len(indices[right]) == 0 { // k个列表里都不含right这个数字
			continue
		}
		for _, index := range indices[right] {
			freq[index]++
			if freq[index] == 1 { // right这个数字在列表index里出现一次了，即列表index至少有一个元素包含在窗口里了
				inside++
			}
		}
		for ; inside == size; left++ {
			if right-left < end-start {
				start, end = left, right
			}
			for _, index := range indices[left] {
				freq[index]--
				if freq[index] == 0 {
					inside--
				}
			}
		}
	}
	return []int{start, end}
}