সি++-এ বিভিন্ন লিস্ট থেকে উপাদান বাছাই করে সর্বনিম্ন পার্থক্য খুঁজে বের করার প্রোগ্রাম

সমস্যা বিবরণ

একাধিক লিস্টের একটি লিস্ট দেওয়া আছে। প্রতিটি লিস্ট থেকে একটি করে উপাদান বাছাই করে তাদের মধ্যে সর্বাধিক ও সর্বনিম্ন মানের পার্থক্য ন্যূনতম করা লক্ষ্য।

উদাহরণ: lists = [[30, 50, 90], [85], [35, 70]] হলে আউটপুট 20। কারণ 90, 85, 70 বাছাই করলে 90 - 70 = 20।

সমাধানের পদ্ধতি

প্রতিটি লিস্টকে সর্ট করুন।
প্রয়োরিটি কিউ (মিন-হিপ) ব্যবহার করুন যেখানে প্রতিটি লিস্টের প্রথম উপাদান রাখা হবে।
maxVal ট্র্যাক করুন বর্তমানে হিপে থাকা সর্বোচ্চ মান।
হিপ থেকে ন্যূনতম উপাদান বের করুন, পার্থক্য maxVal - minVal আপডেট করুন।
সেই লিস্টের পরের উপাদান হিপে পুশ করুন এবং maxVal আপডেট করুন।
যখন কোনো লিস্ট খালি হয়, লুপ বন্ধ করুন।
সর্বনিম্ন পার্থক্য রিটার্ন করুন।

উদাহরণ কোড

#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 main() {
    vector<vector<int>> v = {{30, 50, 90}, {85}, {35, 70}};
    cout << solve(v);
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: {{30, 50, 90}, {85}, {35, 70}}

আউটপুট: 20