সি++ প্রোগ্রাম: কতগুলো কোঅর্ডিনেট পেয়ার তৈরি করা যায় বের করা

মান লিন 2n সংখ্যক কোঅর্ডিনেট দেওয়া আছে ২D প্লেনে। এগুলো দুটি অ্যারে 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,3) এবং (0,2)।

পদ্ধতি (Steps)

chk অ্যারে সাইজ ১০০, ০ দিয়ে আরম্ভিক
coordA সর্ট করুন
coordB সর্ট করুন
k := 0
i = n-1 থেকে 0 পর্যন্ত লুপ (নাম কমাতে):
    j = 0 থেকে n-1 পর্যন্ত লুপ:
        যদি chk[j]==0 এবং coordA[i].first < coordB[j].second এবং coordA[i].second < coordB[j].first হয়, তবে
            chk[j] := 1
            k++
            ব্রেক (ইনার লুপ থেকে)
প্রিন্ট k

উদাহরণ কোড (C++)

#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