題目網址：https://leetcode.cn/problems/smallest-range-covering-elements-from-k-lists/

題意：給一包含 k 個非遞減排列整數 array 的 list nums。找到一最小區間, 使得每個 array 中皆至少有一個整數包含在該區間中。

定義區間 [a, b] < [c, d], 滿足下列其中一個條件便成立：

  • b-a < d-c
  • b-a == d-c 且 a < c

Solution 1：

想法：利用 Sliding Window, 類似 76. Minimum Window Substring

  • 首先, 取出每個 array 中的最小值, 並加入到 set 中
  • 取出 set 中最大、最小的值, 並計算出 newRange
  • 若 newRange < range, 則更新 range 和最小區間
  • 移除 set 中的最小元素, 並將 insert 其所對應的 array 之下一個元素
    若該元素為不存在, 則直接返回

e.g. nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]], 其中 i、j、k 分別代表 idx = 0 ~ 2 的 array 當前 set 中的元素 idx

  • 一開始 i、j、k 皆為 0, set = {0,4,5}。此時 set 中 [最小值, 最大值] 的區間 [0, 5] 可包含每個 array 中的一個整數
  • 移除 set 中的最小元素 0, 並將其對應到的 array 之 ptr + 1, 也就是 j + 1。並將 9 加到 set 中。此時 set = {4, 5, 9}
  • 依此類推, 可參考下圖

為何是移動最小元素的 ptr?

因為如果當前 set 中的 max 不變, 而最小值變大 ➔ 最小區間的範圍會縮小

e.g. 上圖中綠框的部分, 在兩次更新中 max 皆為 24, 但 min 從 18 變成 20

➔ 使得最小區間由 5 變成 4

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        using pii = pair<int, int>;

        const int n = nums.size();
        set<pii> ordered; // 紀錄 set 中元素的 val、對應的 array idx
        vector<int> ptr(n, 0); // 紀錄每個 array 當前在 set 中的元素之 ptr

        // 取每個 array 的第一個元素
        for (int i = 0; i < n; ++i) {
            ordered.emplace(pii{nums[i][0], i});
        }

        vector<int> res;
        int range = INT_MAX;
        while (true) {
            // 取 set 中最小、最大的元素
            int minValue = ordered.begin()->first;
            int maxValue = ordered.rbegin()->first;
            int newRange = maxValue - minValue;

            // 更新區間
            if (newRange < range) {
                range = newRange;
                res = {minValue, maxValue};
            }

            // 要將最小元素從 set 中取出, 並 insert 對應 array 的下一個元素
            int i = ordered.begin()->second;
            ++ptr[i];

            // 如果下一個元素不存在, 則直接返回
            if (ptr[i] == nums[i].size()) {
                break;
            }

            ordered.erase(ordered.begin());
            ordered.emplace(pii{nums[i][ptr[i]], i});
        }

        return res;
    }
};
  • time：$O(nk \cdot log(k))$
    • 假設每個 array 的平均長度為 n, 且總共 k 個 array
    • $O(nk)$：總共 $nk$ 個元素
    • $O(log(k))$：每次 set 新增元素, set 調整成 ordered 的所需時間為 $O(log(k))$, 因為 set.insert() 是用 red-black tree 所實現的。調整成 ordered 才能在 $O(1)$ time 取得 min、max
  • space：$O(k)$ ➔ set 中的元素個數不超過 k

Solution 2：

想法：利用 Heap, 道理同 Solution 1

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        using pii = pair<int, int>;

        const auto cmp = [](const pii& p1, const pii& p2){
            return p1.first > p2.first;
        };

        const int n = nums.size();
        vector<int> ptr(n, 0); // 紀錄每個 array 當前在 heap 中的元素之 ptr

        // min heap, 紀錄 heap 中元素的 val、對應的 array idx
        priority_queue<pii, vector<pii>, decltype(cmp)> q(cmp);

        // 取每個 array 的第一個元素, 並計算最大值
        int maxValue = 0;
        for (int i = 0; i < n; ++i) {
            maxValue = max(maxValue, nums[i][0]);
            q.emplace(pii{nums[i][0], i});
        }

        vector<int> res;
        int range = INT_MAX;

        while (true) {
            // 取 heap 中最小、最大的元素
            const auto [minValue, i] = q.top();
            const int newRange = maxValue - minValue;

            // 更新區間
            if (newRange < range) {
                range = newRange;
                res = {minValue, maxValue};
            }

            // 要將最小元素從 heap 中取出, 並 insert 對應 array 的下一個元素
            ++ptr[i];

            // 如果下一個元素不存在, 則直接返回
            if (ptr[i] == nums[i].size()) {
                break;
            }

            q.pop();
            q.emplace(pii{nums[i][ptr[i]], i});
            maxValue = max(maxValue, nums[i][ptr[i]]); // 維護最大值
        }

        return res;
    }
};
  • time：$O(nk \cdot log(k))$
    • 假設每個 array 的平均長度為 n, 且總共 k 個 array
    • $O(nk)$：總共 $nk$ 個元素
    • $O(log(k))$：heap 每 insert /delete 一個元素所需的時間
  • space：$O(k)$ ➔ heap 中的元素個數不超過 k