最小范围,包括来自每个k列表的至少一个数字

Question

您有已k排序的整数列表.找到包含每个k列表中至少一个数字的最小范围.

例如,

List 1: [4, 10, 13, 14] 

List 2: [0, 9, 15, 18] 

List 3: [5, 18, 22, 30] 

这里最小的范围将是[14, 18]因为它包含了14从list 1,15从list 2,并18从list 3.

我的方法是:

• 只需使用MinHeap并插入K列表中的第一个元素
• 删除min元素并添加相应列表中的下一个元素
• 同时跟踪最大值和最小值,以便我们可以计算最小范围

但我面临的唯一问题是:假设一个列表中没有剩余的元素,我应该在那里完成还是应该继续？

Answer 1

非常好的O(n log n)算法!

你可以在那里完成,因为你永远不会找到满足给定条件的更好的区间"包括每个k列表中至少一个数字的范围".

假设您要保留当前最小值m(某些列表中的最后一个元素),而是从另一个列表中删除某些内容(不是最小值).在这种情况下,范围只能增长(因为范围的最小值由确定m).所以没有必要这样做,你可以停止你的算法.