C++-এ দেয়া পয়েন্ট ধারণ করতে পারা ম্যাক্সিমাম সেগমেন্টের সংখ্যা

দেওয়া কাজ হচ্ছে দেয়া পয়েন্টগুলো ধারণ করতে পারা সেগমেন্টের ম্যাক্সিমাম সংখ্যা বের করা।

একটি অ্যারে a1[] দেওয়া আছে যার আকার n1 এবং দুটি পূর্ণসংখ্যা A এবং B দেওয়া আছে। দেওয়া অ্যারে a1[]- থেকে n1টি লাইন সেগমেন্ট তৈরি করা যায় যাদের শুরুর এবং শেষ পয়েন্ট হলো a1[i] – A এবং a1[i] + B।

আরেকটি অ্যারে a2[] দেওয়া আছে n2 সংখ্যক পয়েন্টের সাথে। এই পয়েন্টগুলো লাইন সেগমেন্টগুলোর সাথে এসাইন করতে হবে যেন যেসব লাইন সেগমেন্টকে পয়েন্ট এসাইন করা হয়েছে তাদের সংখ্যা সর্বোচ্চ হয়। নোট করুন একটি পয়েন্ট শুধু একবার একটি লাইন সেগমেন্টকে এসাইন করা যায়।

উদাহরণ দিয়ে বুঝি:

ইনপুট

a1[] = {1, 4, 5}, a2[] = {2, 8}, A = 1, B = 2

আউটপুট

ব্যাখ্যা − a1[i] – A এবং a1[i] + B ব্যবহার করে যেসব লাইন সেগমেন্ট তৈরি হয় সেগুলো হলো (0, 6) এবং (3, 7)।

অ্যারে a2[]-এর প্রথম পয়েন্ট ২ প্রথম লাইন সেগমেন্টে এসাইন করা যায় কিন্তু পরবর্তী পয়েন্ট ৮ কোনো লাইন সেগমেন্টে এসাইন করা যায় না। তাই শুধু ১টি লাইন সেগমেন্টকে পয়েন্ট এসাইন করা যায় এবং আউটপুট হয় ১।

ইনপুট

a1[] = {1, 2, 3, 4, 6, 7}, a2[] = {2, 5, 6, 8}, A = 0, B = 1

আউটপুট

নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতি নিম্নরূপ

main ফাংশনে ভেক্টর a1 এবং a2 এবং ইন্টিজার A এবং B নির্দিষ্ট মান দিয়ে ইনিশিয়ালাইজ।
n1 এবং n2 ভেরিয়েবল তৈরি করে ভেক্টর a1 এবং a2-এর আকার সংরক্ষণ।
Max() ফাংশনে প্রথমে দুটি ভেক্টর a1 এবং a2 সর্ট করা হয়।
j = 0 এবং ans = 0 ইনিশিয়ালাইজ করা হয় a2 ট্র্যাক রাখতে এবং চূড়ান্ত উত্তর সংরক্ষণের জন্য।
i = 0 থেকে i < n1 পর্যন্ত লুপ।
ফর লুপের ভিতরে while লুপ কন্ডিশন j < n2।
চেক করা হয় if (a1[i] + B < a2[j])। যদি সত্য হয় তবে while লুপ ব্রেক।
অন্যথায় চেক করা হয় if (a2[j] >= a1[i] - A && a2[j] <= a1[i] + B)। যদি সত্য হয় তবে ans এবং j ইনক্রিমেন্ট এবং while লুপ ব্রেক।
উপরের দুটো স্টেটমেন্ট যদি সত্য না হয় তবে শুধু j ইনক্রিমেন্ট।
ans রিটার্ন

উদাহরণ

#include <bits/stdc++.h> 
using namespace std; 

int Max(vector<int> a1, vector<int> a2, int n1, int n2, int A, int B){ 
    //sorting a1 and a2 
    sort(a1.begin(), a1.end()); 
    sort(a2.begin(), a2.end()); 
    int j = 0; 
    int ans = 0; 
    for (int i = 0; i < n1; i++){ 
        // searching for point 
        while (j < n2){ 
            /* If ending point of segment is 
            smaller than the current point*/ 
            if (a1[i] + B < a2[j]) 
                break; 
            //  
            if (a2[j] >= a1[i] - A && a2[j] <= a1[i] + B){ 
                ans++; 
                j++; 
                break; 
            } 
            else 
                j++; 
        } 
    } 
    return ans; 
} 
// main function 
int main(){ 
    int A = 0, B = 1; 
    vector<int> a1 = { 1, 2, 3, 4, 6, 7 }; 
    int n1 = a1.size(); 
    vector<int> a2 = { 2, 5, 6, 8 }; 
    int n2 = a2.size(); 
    cout << Max(a1, a2, n1, n2, A, B); 
    return 0; 
}