মনে করুন, kটি সোর্টেড পূর্ণসংখ্যা তালিকা আছে। আমাদের সবচেয়ে ছোট রেঞ্জ বের করতে হবে যাতে প্রতিটি তালিকা থেকে কমপক্ষে একটি সংখ্যা থাকতে পারে। রেঞ্জ [a,b] ছোট হয় [c,d]-এর চেয়ে যদি b-a < d-c হয় অথবা b-a == d-c হলে a < c হয়।
যেমন, ইনপুট [[4,10,15,25,26],[0,9,14,20],[5,18,24,30]] হলে, আউটপুট [14, 18]।
সমাধানের ধাপসমূহ
- minRange, maxRange, rangeSize, tempMinRange, tempMaxRange ইনিশিয়ালাইজ করুন
- n := nums.size()
- প্রতিটি তালিকার জন্য পয়েন্টার অ্যারে এবং প্রায়োরিটি কিউ pq সংজ্ঞায়িত করুন
- প্রতিটি তালিকার প্রথম উপাদান pq-তে ঢুকান, tempMaxRange আপডেট করুন
- যখন সত্য (infinite loop):
- temp := pq.top(), pq.pop()
- tempMinRange := temp.first, idx := temp.second
- যদি tempMaxRange - tempMinRange < rangeSize হয়, রেঞ্জ আপডেট করুন
- pointers[idx]++
- যদি pointers[idx] == nums[idx].size() হয়, ব্রেক করুন
- অন্যথায় tempMaxRange আপডেট করুন, পরবর্তী উপাদান pq-তে ঢুকান
- আনসার অ্যারে রিটার্ন করুন
উদাহরণ
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){ cout << ""["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } 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; int maxRange = INT_MIN; int rangeSize = INT_MAX; int tempMinRange, tempMaxRange, tempRangeSize; 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){ pair <int, int> 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; } }; 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)); }
ইনপুট
{{4,10,15,25,26},{0,9,14,20},{5,18,24,30}};
আউটপুট
[14, 18, ]
