algorithm - 如何从每个排序列表中选择一个数字，以使最小值和最大值之间的差异尽可能小？

Question

考虑有数字按递增顺序排列的 k 列表。从每个列表中选择一个数字，以使输出列表中的最大数字和最小数字之间的差最小：

list 1-1,3,5,9,10
list 2-2,4,6,8
list 3-7,11,12,13

输出应该是 5,6,7。

5 从 list-l 中选择，6 从 list-2 中选择，7 从 list-3 中选择

由于该列表中最高和最低数字之间的差异是 2，即 7-5，因此考虑存在 k 列表。

Answer 1

我可以解决这个问题O(N*LogK)，这N是 k 个列表中的数字总数。

1、为每个列表维护一个指针，从0开始。

2、以当前指针为你选择的数字，更新答案。

3、选择编号最小的那一项，加一（只要没有到达该列表的末尾），如果可能，返回第2步，否则终止。

在第 2 步和第 3 步中，使用堆来维持最小数量和最大数量，从而减少从O(K)到的时间O(LogK)。