C++-এ Kটি সর্টেড লিস্ট থেকে সবচেয়ে ছোট রেঞ্জ খুঁজে বের করা

সমস্যা

kটি সর্টেড লিস্ট দেওয়া। এমন সবচেয়ে ছোট রেঞ্জ [a,b] খুঁজুন যাতে প্রতিটি লিস্ট থেকে কমপক্ষে একটা এলিমেন্ট থাকে। রেঞ্জ ছোট বলতে b-a মিনিমাম।

অ্যালগরিদম: Min-Heap + পয়েন্টারস

1. প্রতিটি লিস্টের প্রথম এলিমেন্ট মিন-হিপে পুশ করুন: {value, list_index}।
2. বর্তমান ম্যাক্সimum ট্র্যাক করুন।
3. হিপ খালি না হওয়া পর্যন্ত:
   • হিপ থেকে মিনিমাম বের করুন (minVal, idx)।
   • রেঞ্জ আপডেট: যদি currentMax - minVal < bestRange হয়।
   • সেই লিস্টের (idx) পরবর্তী এলিমেন্ট হিপে পুশ করুন। currentMax আপডেট করুন।
   • যদি কোনো লিস্ট শেষ হয়, ব্রেক করুন।

C++ কোড (সংক্ষিপ্ত)

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 n = nums.size();
        vector<int> ptr(n, 0);
        priority_queue<pair<int,int>, vector<pair<int,int>>, Comparator> pq;
        int curMax = INT_MIN;
        for (int i=0; i

উদাহরণ আউটপুট
Input: [[4,10,15,25,26],[0,9,14,20],[5,18,24,30]]
Output: [14, 18]