ধরুন আমরা শিশুদের কিছু কুকি বিতরণ করার চেষ্টা করছি৷ তবে, আমাদের প্রতিটি শিশুকে সর্বাধিক একটি কুকি দেওয়া উচিত। এখন প্রতিটি শিশুর একটি লোভ ফ্যাক্টর জিআই রয়েছে, যা একটি কুকির ন্যূনতম আকার যা শিশুটি সন্তুষ্ট হবে; এবং প্রতিটি কুকি j একটি আকার sj আছে. যখন sj>=gi, তখন আমরা চাইল্ড iকে কুকি j বরাদ্দ করতে পারি, এবং শিশু i সন্তুষ্ট হবে। আমাদের লক্ষ্য হল শিশুদের সামগ্রীর সংখ্যা সর্বাধিক করা এবং সর্বাধিক সংখ্যা আউটপুট করা।
সুতরাং, যদি ইনপুটটি [1,2], [1,2,3] এর মত হয়, তাহলে আউটপুট হবে 2, সেখানে 2টি শিশু এবং 3টি কুকি রয়েছে। 2টি বাচ্চার লোভের কারণ হল 1, 2। এখন আমাদের কাছে 3টি কুকি আছে এবং তাদের সাইজ সব বাচ্চাদের খুশি করার জন্য যথেষ্ট বড়, তাই আউটপুট হল 2।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
অ্যারে সাজান g
-
অ্যারে s
সাজান -
i :=0, j =0
-
যখন (i
করুন -
যদি g[i] <=s[j] হয়, তাহলে −
-
(i 1 দ্বারা বাড়ান)
-
-
(j 1 দ্বারা বাড়ান)
-
-
ফেরত i
উদাহরণ
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int i = 0, j = 0;
while (i < g.size() && j < s.size()) {
if (g[i] <= s[j])
i++;
j++;
}
return i;
}
};
main(){
Solution ob;
vector<int> v = {1,2}, v1 = {1,2,3};
cout << (ob.findContentChildren(v, v1));
} ইনপুট
{1,2}, {1,2,3} আউটপুট
2
