C++ में दो ऐरे से अद्वितीय पेयर्स को अधिकतम करना

समस्या कथन

दो समान आकार N के ऐरे दिए गए हैं, उनके तत्वों का उपयोग करके अधिकतम संख्या में पेयर्स बनाएं, एक पहले ऐरे से और दूसरा दूसरे ऐरे से, जैसे कि प्रत्येक ऐरे से एक तत्व अधिकतम एक बार उपयोग किया जाता है और चुने गए तत्वों के बीच निरपेक्ष अंतर दिए गए तत्व K से कम या बराबर होता है।

उदाहरण

यदि इनपुट है:

arr1[] = {3, 4, 5, 2, 1}

arr2[] = {6, 5, 4, 7, 15}

और k = 3 तो हम निम्न 4 पेयर्स बना सकते हैं जिनका निरपेक्ष अंतर 3 से कम या बराबर है:

(1, 4), (2, 5), (3, 6), (4, 7)

एल्गोरिदम

हम इस समस्या को हल करने के लिए पुनरावर्ती दृष्टिकोण का उपयोग कर सकते हैं:

• दोनों ऐरे को सॉर्ट करें।
• पहले ऐरे के प्रत्येक तत्व की तुलना दूसरे ऐरे के प्रत्येक तत्व से संभावित पेयर के लिए करें, यदि पेयर बनाना संभव है।
• पहले ऐरे के अगले तत्व के लिए अगले संभावित पेयर की जांच जारी रखें।

उदाहरण

#include <bits/stdc++.h>
using namespace std;

int getMaxUniquePairs(int* arr1, int* arr2, int n, int k) {
    sort(arr1, arr1 + n);
    sort(arr2, arr2 + n);
    bool visited[n];
    memset(visited, false, sizeof(visited));
    int pairCnt = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (abs(arr1[i] - arr2[j]) <= k && visited[j] == false) {
                ++pairCnt;
                visited[j] = true;
                break;
            }
        }
    }
    return pairCnt;
}

int main() {
    int arr1[] = {3, 4, 5, 2, 1};
    int arr2[] = {6, 5, 4, 7, 15};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    int k = 3;
    cout << "Maximum unique pairs = " << getMaxUniquePairs(arr1, arr2, n, k) << endl;
    return 0;
}

आउटपुट

Maximum unique pairs = 4