ช่วงเล็กที่สุดครอบคลุม K ลิสต์ (Smallest Range Covering Elements from K Lists) ใน C++

ภาพรวมปัญหา

มี k ลิสต์จำนวนเต็มที่เรียงแล้ว หาช่วง [a,b] ที่เล็กที่สุดที่มีอย่างน้อย 1 ตัวจากแต่ละลิสต์ ช่วง [a,b] เล็กกว่า [c,d] ถ้า b-a < d-c หรือ a < c ถ้าเท่ากัน

ตัวอย่าง

[[4,10,15,25,26], [0,9,14,20], [5,18,24,30]] → [14, 18]

แนวทางแก้ปัญหา (K-way Merge + Priority Queue)

• ใช้ Min-Heap เก็บ (ค่า, index ของลิสต์)
• เริ่มต้น push ตัวแรกของแต่ละลิสต์ ติดตาม max ปัจจุบัน
• ซ้ำ: pop min ออก → อัปเดตช่วง [min, max] ถ้าเล็กกว่าคำตอบปัจจุบัน
• push ตัวถัดไปจากลิสต์เดียวกัน อัปเดต max
• หยุดเมื่อลิสต์ไหนหมด

ตัวอย่างโปรแกรม

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

struct Comparator {
    bool operator()(pair<int, int> a, pair<int, int> b) {
        return !(a.first < b.first);
    }
};

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        int minRange = INT_MAX, maxRange = INT_MIN, rangeSize = INT_MAX;
        int tempMinRange, tempMaxRange;
        tempMinRange = INT_MAX; tempMaxRange = INT_MIN;
        
        int n = nums.size();
        vector<int> pointers(n);
        priority_queue<pair<int, int>, vector<pair<int, int>>, Comparator> pq;
        
        for(int i = 0; i < n; i++) {
            pq.push({nums[i][0], i});
            tempMaxRange = max(tempMaxRange, nums[i][0]);
        }
        
        while(1) {
            auto temp = pq.top(); pq.pop();
            tempMinRange = temp.first;
            int idx = temp.second;
            
            if(tempMaxRange - tempMinRange < rangeSize) {
                rangeSize = tempMaxRange - tempMinRange;
                minRange = tempMinRange;
                maxRange = tempMaxRange;
            }
            
            pointers[idx]++;
            if(pointers[idx] == nums[idx].size()) break;
            else {
                tempMaxRange = max(tempMaxRange, nums[idx][pointers[idx]]);
                pq.push({nums[idx][pointers[idx]], idx});
            }
        }
        
        vector<int> ans(2);
        ans[0] = minRange; ans[1] = maxRange;
        return ans;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{4,10,15,25,26},{0,9,14,20},{5,18,24,30}};
    // print_vector(ob.smallestRange(v));
}

Input

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

Output

[14, 18]