最小範圍列出

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，並且從list 318。

MY的做法是：

• 只需使用一個MinHeap和從K列表
• 插入所述第一元件中取出最小元素，並從相應的列表中添加的下一個元素
• 同時跟蹤最大和最小值，以便我們可以計算最小範圍

但唯一的問題我面對的是：假設對於一個列表，我應該在那裏完成還是不應該繼續？

Answer 1

非常好的爲O（n log n）的算法！

可以完成，因爲你永遠不會找到更好的間隔滿足給定的條件「的範圍，包括從每個k個清單中的至少一個數字」。

假設你在（從一些列表中的最後一個元素）離開目前的最低m，而是要卸下從另一個列表中的東西（不是最小）。在這種情況下，範圍只能增長（因爲範圍的最小值由m決定）。所以這樣做沒有意義，你可以停止你的算法。

Answer 2

不，這不是你的終止條件。請看下面的例子：

1: [0] 
2: [1] 

範圍是很清楚[0,1]，但如果你一旦你發現一個空錶停了，你將返回[0,0]。

因此，只有當您知道您已經看到所有k列表中的值和時，才能停止其中一個列表已用完的項目。如果您要分別跟蹤每個列表的最小值和最大值，這應該很容易，因爲您可以確保每個列表都有一些最小值和最大值。