题目描述

你有 k 个升序排列的整数数组。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。

我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。

样例

输入:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
输出: [20,24]
解释: 
列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。

注意

1. 给定的列表可能包含重复元素，所以在这里升序表示 >= 。
2. 1 <= k <= 3500
3. $-10^5$ <= 元素的值 <= $10^5$
4. 对于使用Java的用户，请注意传入类型已修改为List<List<Integer>>。重置代码模板后可以看到这项改动。

算法

(多指针，堆) $O(n \log k)$

1. 可以很容易的看出，答案的区间左右端点一定是某两个序列中的某两个数。
2. 初始化 k 个指针指向每个列表的首元素，并将其和所在列表的序号合并为 pair 加入到小根堆中，并记录这 k 个数的最大值。
3. 每次从小根堆中弹出最小值，和此时的最大值构成的区间就构成一个候选的答案。
4. 接着，最小值所在列表的指针向后移动，加入新的数字到堆中，并更新此时的最大值。
5. 不断按照以上操作，直到某个指针到达了序列末尾为止。

时间复杂度

• 堆的大小为 $O(k)$，在遍历所有数字时都会进行对堆的操作，故时间复杂度为 $O(n \log k)$。

C++ 代码

class Solution {
public:
    #define PI pair<int, int>
    vector<int> smallestRange(vector<vector<int>>& nums) {
        int k = nums.size();
        priority_queue<PI, vector<PI>, greater<PI>> heap;
        vector<int> ans(2), p(k, 0);
        int min_length = INT_MAX, right = INT_MIN;
        for (int i = 0; i < k; i++) {
            heap.push(make_pair(nums[i][0], i));
            right = max(right, nums[i][0]);
        }

        while (1) {
            PI it_min = heap.top();
            heap.pop();
            int left = it_min.first;
            if (min_length > right - left) {
                min_length = right - left;
                ans[0] = left;
                ans[1] = right;
            }
            int which_min = it_min.second;
            if (p[which_min] == nums[which_min].size() - 1)
                break;
            p[which_min]++;
            right = max(right, nums[which_min][p[which_min]]);
            heap.push(make_pair(nums[which_min][p[which_min]], which_min));
        }
        return ans;
    }
};