法国我，怎么是hard
我不想写每日了
632. Smallest Range Covering Elements from K Lists
有k个lists依照non-decreasing的方式排列
请找到最小的range 可以包含所有lists至少一个元素
定义[a,b]比[c,d]小，b-a < d-c 或是 a<c如果 b-a == d-c
思路:
(1)可以用merge sort把所有list合在一起，再用sliding windows去找最小range
(2)
用minimun heap，从每个list抓一个元素放到heap里
并记录最大值
每次都从heap pop中一个元素，如果pop出来的元素属于lists[i]
就再从lists[i] push一个元素进去
并且看目前heap里的最大值和最小值相差多少
每次都要更新最大值
这样也可以得到答案
golang code :
type IntHeap [][2]int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) {
// Push and Pop use pointer receivers because they modify the slice's length,
// not just its contents.
*h = append(*h, x.([2]int))
}
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func smallestRange(nums [][]int) []int {
idx, min_diff, ans := make([]int, len(nums)), math.MaxInt64, []int{math.
MaxInt64, math.MinInt64}
min_heap := &IntHeap{}
for i := 0; i < len(nums); i++ {
idx[i] = 1
heap.Push(min_heap, [2]int{nums[i][0], i})
ans[1] = max(ans[1], nums[i][0])
}
ans[0] = (*min_heap)[0][0]
rec := ans[1]
min_diff = ans[1] - ans[0]
for {
tmp := heap.Pop(min_heap).([2]int)
if idx[tmp[1]] == len(nums[tmp[1]]) {
break
} else {
heap.Push(min_heap, [2]int{nums[tmp[1]][idx[tmp[1]]], tmp[1]})
rec = max(rec, nums[tmp[1]][idx[tmp[1]]])
if rec-(*min_heap)[0][0] < min_diff {
min_diff = rec - (*min_heap)[0][0]
ans[0] = (*min_heap)[0][0]
ans[1] = rec
}
idx[tmp[1]]++
}
}
return ans
}