मान लीजिए, हमें द्वि-विमीय तल पर निर्देशांकों की 2n संख्या दी गई है। 2n निर्देशांक दो सरणियों कोर्डए, और कोऑर्डबी में विभाजित हैं। निर्देशांक पूर्णांक जोड़े के रूप में दर्शाए जाते हैं। अब हमें निर्देशांक युग्म बनाने हैं जिनमें निर्देशांक A से एक बिंदु और समन्वय B से एक बिंदु होगा। हम जोड़े बना सकते हैं यदि और केवल यदि समन्वय से बिंदु का x निर्देशांक समन्वयक से बिंदु से छोटा है, और समन्वय से बिंदु का y निर्देशांक समन्वयक से बिंदु से छोटा है। हमें यह पता लगाना है कि हम कितने जोड़े बना सकते हैं, और एक बिंदु कई जोड़े से संबंधित नहीं हो सकता है।
इसलिए, यदि इनपुट n =3 जैसा है, तो कोर्ड्सए ={{1, 3}, {2, 4}, {4, 3}}, कॉर्ड्सबी ={{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