C++ में विभिन्न सूचियों से चुने गए तत्वों का न्यूनतम अंतर ढूंढने का प्रोग्राम

समस्या विवरण

मान लीजिए हमारे पास सूचियों की एक सूची है, हमें प्रत्येक सूची से एक मान चुनकर बनने वाले सबसे छोटे अंतर को ढूंढना है और चुने गए तत्वों के अधिकतम और न्यूनतम संख्या का अंतर लेना है।

उदाहरण के लिए, यदि इनपुट है lists = [[30, 50, 90], [85], [35, 70]], तो आउटपुट 20 होगा, क्योंकि हम 90, 85, 70 ले सकते हैं और 90 - 70 = 20 होगा।

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

1. maxVal := -अनंत
2. ret := अनंत
3. एक प्राथमिकता कतार pq परिभाषित करें
4. n := सूचियों का आकार
5. i := 0 से n-1 तक:
   • lists[i] को सॉर्ट करें
   • {lists[i][0], i, 0} को pq में डालें
   • maxVal := max(lists[i][0], maxVal)
6. जब तक pq का आकार n के बराबर है:
   • temp := pq का शीर्ष तत्व
   • pq से शीर्ष तत्व हटाएं
   • ret := min(ret, maxVal - temp[0])
   • temp के अंतिम तत्व को बढ़ाएं
   • यदि temp का अंतिम तत्व < lists[temp[1]] का आकार:
     • maxVal := max(maxVal, lists[temp[1]][temp का अंतिम तत्व])
     • temp[0] := lists[temp[1]][temp का अंतिम तत्व]
     • temp को pq में डालें
7. ret वापस करें

उदाहरण

#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