如何用堆求覆盖 K 个有序列表的最小区间？

简化版

覆盖 K 个有序列表的最小区间，可以用小顶堆维护每个列表当前选中的元素，同时维护当前最大值。

每次用堆取出当前最小值，此时 [min, currentMax] 就是一个覆盖所有列表的候选区间。然后推进最小值所在列表的指针，继续尝试缩小区间。

当某个列表耗尽时，就无法再覆盖所有 K 个列表，算法结束。

详细版

堆中保存：

(value, listIndex, elementIndex)

初始化时，把每个列表的第一个元素放入小顶堆，并记录当前最大值 maxVal。

循环过程：

弹出堆顶最小值 minVal；
用 [minVal, maxVal] 更新答案；
将该元素所在列表的下一个元素入堆；
更新 maxVal；
如果该列表没有下一个元素，停止。

指标	复杂度
堆大小	`K`
每步操作	`O(log K)`
总时间	`O(N log K)`

完整版教学

1. 题目本质是什么

题目要求找一个区间 [L, R]，使它至少包含每个列表中的一个数，并且区间尽量短。

例如：

A: 4, 10, 15
B: 1, 12, 20
C: 7, 13, 18

如果当前选中 4, 1, 7，那么覆盖这三个列表的区间是 [1, 7]。

目标是不断调整每个列表当前选中的元素，使最大值和最小值的差尽量小。

2. 为什么用小顶堆

任意时刻，我们从每个列表选一个元素。

这些元素的最大值和最小值决定当前区间。

最大值可以用变量 maxVal 维护；
最小值需要频繁取出，所以用小顶堆。

这个问题的堆不是为了排序全部元素，而是维护 K 个当前候选中的最小值。

3. 为什么每次推进最小值所在列表

当前区间是 [minVal, maxVal]。

如果想缩小区间，左边界必须变大。唯一能让左边界变大的办法，就是丢掉当前最小值，推进它所在列表。

如果推进其他列表，minVal 不变，区间左边界不会变大，通常无法获得更短区间。

这就是算法贪心推进的依据。

4. 初始化为什么每个列表放一个元素

区间必须覆盖所有列表。

所以初始状态至少要从每个列表选一个元素。最自然的选择是每个列表的第一个元素。

heap = [(list0[0], 0, 0), (list1[0], 1, 0), ...]
maxVal = max(all first values)

只要堆里还有 K 个元素，就说明当前区间仍然覆盖所有列表。

5. 什么时候停止

当弹出的元素所在列表没有下一个元素时，算法停止。

原因是：如果这个列表无法再提供候选值，之后就不可能形成覆盖所有列表的区间。

情况	是否继续
所在列表还有下一个元素	继续
所在列表耗尽	停止

停止前已经评估过当前区间，所以不会漏掉答案。

6. 区间比较规则怎么写

通常先比较长度，再比较左端点。

if R - L < bestR - bestL:
  update
else if R - L == bestR - bestL and L < bestL:
  update

如果题目没有要求左端点更小，至少要保证长度比较正确。

面试时可以主动说明 tie-breaker，体现边界意识。

7. 和合并 K 个有序链表的关系

这道题和多路归并非常像。

区别是：

问题	堆顶弹出后做什么
合并 K 个有序链表	直接输出堆顶
最小覆盖区间	用堆顶和当前最大值更新区间

两者都利用了「每个有序序列保留一个当前候选」的思想。

8. 常见误区与追问

误区：要枚举所有区间。 有序列表可以用堆和指针推进，不需要暴力枚举。
误区：每次应该推进最大值所在列表。 缩小区间要提高左边界，所以应推进当前最小值所在列表。
误区：只维护最小值就够了。 区间右端点还需要当前最大值，所以要额外维护 maxVal。
追问：为什么堆大小始终是 K？ 因为每个列表只放一个当前候选，覆盖所有列表时正好 K 个。
追问：某个列表耗尽为什么停止？ 因为后续无法再从这个列表选元素，覆盖条件无法满足。

简化版

详细版