ধরুন আমাদের কাছে তালিকার একটি তালিকা আছে, আমাদেরকে ক্ষুদ্রতম পার্থক্যটি খুঁজে বের করতে হবে যা প্রতিটি তালিকা থেকে একটি মান বাছাই করে এবং বাছাই করা উপাদানের সর্বাধিক এবং সর্বনিম্ন সংখ্যার মধ্যে পার্থক্য নিয়ে গঠিত হতে পারে।
সুতরাং, যদি ইনপুটটি তালিকার মত হয় =[ [[30, 50, 90], [85], [35, 70]], তাহলে আউটপুট হবে 20, যেমন আমরা নিতে পারি 90, 85, 70 এবং 90 - 70 =২০
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
maxVal :=-inf
-
ret :=inf
-
একটি অগ্রাধিকার সারি সংজ্ঞায়িত করুন pq
-
n :=তালিকার আকার
-
আরম্ভ করার জন্য i :=0, যখন i
-
অ্যারে তালিকাগুলি সাজান[i]
-
pq
-এ {তালিকা[i, 0], i, 0} ঢোকান -
maxVal :=তালিকার সর্বাধিক [i, 0] এবং maxVal
-
-
pq-এর আকার n-এর সমান হলে, −
করুন-
একটি অ্যারে temp =pq এর শীর্ষ
সংজ্ঞায়িত করুন -
pq
থেকে শীর্ষ উপাদান মুছুন -
ret :=ret এর সর্বনিম্ন এবং (maxVal - temp[0])
-
তাপমাত্রার শেষ উপাদান বাড়ান
-
যদি temp এর শেষ উপাদান <তালিকার আকার[temp[1]], তাহলে <
-
maxVal :=সর্বোচ্চ maxVal এবং তালিকা[temp[1], temp-এর শেষ উপাদান]
-
temp[0] :=তালিকা[temp[1], টেম্পের শেষ উপাদান]
-
pq
-এ তাপমাত্রা সন্নিবেশ করান
-
-
-
রিটার্ন রিটার্ন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
struct Cmp {
bool operator()(vector<int>& a, vector<int>& b) {
return !(a[0] < b[0]);
}
};
class Solution {
public:
int solve(vector<vector<int>>& lists) {
int maxVal = INT_MIN;
int ret = INT_MAX;
priority_queue<vector<int>, vector<vector<int>>, Cmp> pq;
int n = lists.size();
for (int i = 0; i < n; i++) {
sort(lists[i].begin(), lists[i].end());
pq.push({lists[i][0], i, 0});
maxVal = max(lists[i][0], maxVal);
}
while (pq.size() == n) {
vector<int> temp = pq.top();
pq.pop();
ret = min(ret, maxVal - temp[0]);
temp.back()++;
if (temp.back() < lists[temp[1]].size()) {
maxVal = max(maxVal, lists[temp[1]][temp.back()]);
temp[0] = lists[temp[1]][temp.back()];
pq.push(temp);
}
}
return ret;
}
};
int solve(vector<vector<int>>& lists) {
return (new Solution())->solve(lists);
}
int main(){
vector<vector<int>> v = {{30, 50, 90},{85},{35, 70}};
cout << solve(v);
} ইনপুট
{{30, 50, 90},{85},{35, 70}} আউটপুট
20
