मान लीजिए, हमें एक दो-आयामी तल पर 2n संख्या में कोऑर्डिनेट्स दिए गए हैं। 2n कोऑर्डिनेट्स को दो ऐरे coordA और coordB में विभाजित किया गया है। कोऑर्डिनेट्स को पूर्णांक जोड़े के रूप में दर्शाया गया है। अब हमें कोऑर्डिनेट जोड़े बनाने हैं जिनमें coordA से एक पॉइंट और coordB से एक पॉइंट होगा। हम जोड़े तभी बना सकते हैं जब coordA के पॉइंट का x कोऑर्डिनेट coordB के पॉइंट के x कोऑर्डिनेट से छोटा हो, और coordA के पॉइंट का y कोऑर्डिनेट coordB के पॉइंट के y कोऑर्डिनेट से छोटा हो। हमें बनाए जा सकने वाले जोड़ों की संख्या ढूंढनी है, और एक पॉइंट कई जोड़ों से संबंधित नहीं हो सकता।
इसलिए, यदि इनपुट इस तरह है: 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
