หา Smallest Range ที่ครอบคลุม Element จาก K Lists ใน C++

โจทย์: กำหนด K sorted lists หา range [a,b] ที่เล็กที่สุด (b-a น้อยที่สุด tie-break a น้อยที่สุด) ที่มีอย่างน้อย 1 element จากแต่ละ list

ตัวอย่าง: [[4,10,15,25,26],[0,9,14,20],[5,18,24,30]] → [14,18]

อัลกอริธึม: Min-Heap + Sliding Window

1. Push element แรกของแต่ละ list เข้า min-heap (value, list_index)
2. Track current_max ของ elements ใน heap 3. วนลูป:
• Pop min element → ได้ current_min
• Update best range ถ้า current_max - current_min น้อยกว่า
• Advance pointer ใน list นั้น Push element ถัดไป Update current_max
• ถ้าหมด list ไหน → หยุด

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

struct Comparator {
    bool operator()(pair<int,int> a, pair<int,int> b) {
        return a.first > b.first; // min-heap
    }
};

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        int minRange = INT_MAX, maxRange = INT_MIN, rangeSize = INT_MAX;
        int n = nums.size();
        vector<int> pointers(n, 0);
        priority_queue<pair<int,int>, vector<pair<int,int>>, Comparator> pq;
        int current_max = INT_MIN;
        for (int i = 0; i < n; i++) {
            pq.push({nums[i][0], i});
            current_max = max(current_max, nums[i][0]);
        }
        while (true) {
            auto [current_min, idx] = pq.top(); pq.pop();
            if (current_max - current_min < rangeSize) {
                rangeSize = current_max - current_min;
                minRange = current_min;
                maxRange = current_max;
            }
            pointers[idx]++;
            if (pointers[idx] == nums[idx].size()) break;
            int next_val = nums[idx][pointers[idx]];
            current_max = max(current_max, next_val);
            pq.push({next_val, idx});
        }
        return {minRange, maxRange};
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{4,10,15,25,26},{0,9,14,20},{5,18,24,30}};
    auto ans = ob.smallestRange(v);
    cout << "[" << ans[0] << ", " << ans[1] << "]";
}

อินพุต

{{4,10,15,25,26},{0,9,14,20},{5,18,24,30}}

เอาต์พุท

[14, 18]

Complexity

• Time: O(N log K) โดย N = total elements, K = จำนวน lists
• Space: O(K)