C++ এ k তালিকা থেকে উপাদান ধারণকারী ক্ষুদ্রতম পরিসর খুঁজুন

ধরুন আমাদের k বিভিন্ন তালিকা আছে। উপাদানগুলি সাজানো হয়। আমাদের ক্ষুদ্রতম পরিসরটি অনুসন্ধান করতে হবে যাতে প্রতিটি k বিভিন্ন তালিকা থেকে কমপক্ষে একটি সংখ্যা অন্তর্ভুক্ত থাকে। এখানে [a,b] পরিসর [c,d] থেকে ছোট যখন b-a

সুতরাং ইনপুট যদি [[4,10,15,25,26],[0,9,14,20],[5,18,24,30]] এর মত হয়, তাহলে আউটপুট হবে [14, 18]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• minRange :=inf, maxRange :=-inf, rangeSize :=inf, tempMinRange :=inf, tempMaxRange :=-inf

• n :=সংখ্যার আকার

• n

  আকারের একটি অ্যারে পয়েন্টার সংজ্ঞায়িত করুন

• একটি অগ্রাধিকার সারি তৈরি করুন pq

• আরম্ভ করার জন্য i :=0, যখন i

  • pq

    -এ { nums[i, 0], i } ঢোকান

  • tempMaxRange :=সর্বোচ্চ tempMaxRange এবং সংখ্যা[i, 0]

• যখন 1 অ-শূন্য, কর −

  • এক জোড়া তাপমাত্রা সংজ্ঞায়িত করুন :=pq এর শীর্ষ

  • pq

    থেকে উপাদান মুছুন

  • tempMinRange :=temp.first

  • idx :=তাপমাত্রার দ্বিতীয় উপাদান

  • যদি tempMaxRange - tempMinRange

    • rangeSize :=tempMaxRange - tempMinRange

    • minRange :=tempMinRange

    • maxRange :=tempMaxRange

  • (পয়েন্টার [idx] 1 দ্বারা বৃদ্ধি করুন)

  • যদি পয়েন্টার[idx] সংখ্যার আকারের [idx] সমান হয়, তাহলে −

    • লুপ থেকে বেরিয়ে আসুন

  • অন্যথায়

    • tempMaxRange :=সর্বোচ্চ tempMaxRange এবং সংখ্যা[idx, pointers[idx]]

    • pq এ { nums[idx, pointers[idx]], idx } সন্নিবেশ করুন

• আকার 2

  এর একটি অ্যারে উত্তর সংজ্ঞায়িত করুন

• ans[0] :=minRange, ans[1] :=maxRange

• উত্তর ফেরত দিন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#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, ]