সমস্যা বিবরণ
সমান আকার N-এর দুটি অ্যারে দেওয়া আছে, তাদের উপাদান ব্যবহার করে সর্বোচ্চ সংখ্যক যুগল তৈরি করতে হবে, একটি প্রথম অ্যারে থেকে এবং অন্যটি দ্বিতীয় অ্যারে থেকে, যাতে প্রতিটি অ্যারে থেকে একটি উপাদান সর্বোচ্চ একবার ব্যবহার হয় এবং বাছাই করা উপাদান দুটির απόলোক বিচ্ছেদ দেওয়া একটি উপাদান K-এর চেয়ে কম বা সমান হয়।
উদাহরণ
যদি ইনপুট হয়:
arr1[] = {3, 4, 5, 2, 1}
arr2[] = {6, 5, 4, 7, 15}
এবং k = 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
