包含每个k个列表中至少一个数字的最小范围

Question

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

例如，

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

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

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

这里最小的区间应为[14,18]，因为它包含list 1中的14，list 2中的15以及list 3中的18。

我的方法是：

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

但是我面临的唯一问题是：假设一个列表没有更多的元素，那么我应该停止还是继续？

- Trying

---

当从堆中取出最小元素且对应的列表为空时，应停止操作。 - Толя

这种方法怎么样： 1）收集每个列表的起始点和结束点。 2）根据它们的起始点进行排序。 3）遍历排序后的对 考虑重叠和非重叠对的情况，并找到最小间隔。如果这种方法有误，请纠正我。 - Chandan

抱歉，我看错了问题，请忽略。我们还需要注意单个元素。 - Chandan

Answer 1

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

你可以在这里结束，因为你将永远无法找到更好的区间来满足给定条件“包括k个列表中至少一个数字的范围”。

假设你离开当前的最小值m（某个列表的上一个元素），而是从另一个列表中删除某个元素（不是最小值）。在这种情况下，范围只能增加（因为范围的最小值由m确定）。因此，这样做没有意义，你可以停止算法。

- Łukasz Kidziński

Answer 2

不，那不是你的终止条件。看看这个例子：

1: [0]
2: [1]

范围很明显是[0,1]，但如果你在检测到空列表时立即停止，那么你将返回[0,0]。

因此，只有当您知道已经从所有k个列表中看到了值并且其中一个列表已经用完项目时，才能停止。如果您分别跟踪每个列表的最小值和最大值，那么这应该很容易，因为您可以确保每个列表都有一些最小值和最大值。

- amnn

---

但是OP最初通过从所有k个列表中取第一个元素来创建大小为k的小根堆。这将涵盖上述情况并返回正确的范围。 - dark_shadow

我仍然不相信这是真的，因为无论在最小堆中剩下什么，给定条件仍将返回一个 [0,0] 区间。 - amnn