समस्या कथन
समान आकार 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