ধরুন, একটি দ্বি-মাত্রিক সমতলে আমাদের 2n সংখ্যক স্থানাঙ্ক দেওয়া হয়েছে। 2n স্থানাঙ্ক দুটি অ্যারে coordA এবং coordB এ বিভক্ত। স্থানাঙ্কগুলিকে পূর্ণসংখ্যা জোড়া হিসাবে উপস্থাপন করা হয়। এখন আমাদের স্থানাঙ্ক জোড়া তৈরি করতে হবে যাতে coordA থেকে একটি বিন্দু এবং coordB থেকে একটি বিন্দু থাকবে। আমরা জোড়া তৈরি করতে পারি যদি এবং শুধুমাত্র যদি coordA থেকে বিন্দুর x স্থানাঙ্ক coordB থেকে বিন্দুর চেয়ে ছোট হয় এবং coordA থেকে বিন্দুর y স্থানাঙ্ক coordB থেকে বিন্দুর চেয়ে ছোট হয়। আমরা কত জোড়া জোড়া তৈরি করতে পারি তা খুঁজে বের করতে হবে, এবং একটি বিন্দু একাধিক জোড়ার অন্তর্গত হতে পারে না।
সুতরাং, যদি ইনপুটটি n =3 এর মত হয়, coordsA ={{1, 3}, {2, 4}, {4, 3}}, coordsB ={{2, 2}, {4, 2}, {0 , 2}}, তাহলে আউটপুট হবে 1.
একমাত্র জোড়া তৈরি করা যেতে পারে (1, 3) এবং (0, 2)।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
Define an array chk of size: 100 initialized with 0 sort the array coordA sort the array coordB k := 0 for initialize i := n - 1, when i >= 0, update (decrease i by 1), do: for initialize j := 0, when j < n, update (increase j by 1), do: if chk[j] is same as 0 and first value of coordA[i] < second value of coordB[j] and second value of coordA[i] < first value of coordB[j], then: chk[j] := 1 (increase k by 1) Come out from the loop print(k)
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
#define N 100
void solve(int n, vector<pair<int,int>> coordA, vector<pair<int,int>>coordB){
int i, j, k;
int chk[100] = {0};
sort(coordA.begin(),coordA.end());
sort(coordB.begin(),coordB.end());
k = 0;
for(i = n - 1; i >= 0; i--) {
for(j = 0; j < n; j++) {
if(chk[j] == 0 && coordA[i].first < coordB[j].second && coordA[i].second < coordB[j].first) {
chk[j] = 1;
k++;
break;
}
}
}
cout<< k;
}
int main() {
int n = 3;
vector<pair<int,int>> coordsA = {{1, 3}, {2, 4}, {4, 3}};
vector<pair<int,int>> coordsB = {{2, 2}, {4, 2}, {0, 2}};
solve(n, coordsA, coordsB);
return 0;
} ইনপুট
3, {{1, 3}, {2, 4}, {4, 3}}, {{2, 2}, {4, 2}, {0, 2}} আউটপুট
1
