समस्या विवरण
मान लीजिए हम बच्चों को कुकीज़ वितरित करने का प्रयास कर रहे हैं। लेकिन, हमें प्रत्येक बच्चे को अधिकतम एक कुकी देनी चाहिए। अब प्रत्येक बच्चे i का एक लालच कारक gi होता है, जो कुकी का न्यूनतम आकार है जिससे बच्चा संतुष्ट होगा; और प्रत्येक कुकी j का आकार sj होता है। जब sj >= gi, तो हम कुकी j को बच्चे i को असाइन कर सकते हैं, और बच्चा i संतुष्ट होगा। हमारा लक्ष्य संतुष्ट बच्चों की संख्या को अधिकतम करना और अधिकतम संख्या को आउटपुट करना है।
उदाहरण
यदि इनपुट है: [1,2], [1,2,3], तो आउटपुट होगा 2, क्योंकि 2 बच्चे और 3 कुकीज़ हैं। 2 बच्चों के लालच कारक 1, 2 हैं। अब हमारे पास 3 कुकीज़ हैं और उनके आकार सभी बच्चों को संतुष्ट करने के लिए पर्याप्त बड़े हैं, इसलिए आउटपुट 2 है।
हल करने का दृष्टिकोण
इस समस्या को हल करने के लिए निम्नलिखित चरणों का पालन करें:
- सरणी g को सॉर्ट करें
- सरणी s को सॉर्ट करें
- i := 0, j = 0
- जब (i < g का आकार और j < s का आकार):
- यदि g[i] <= s[j], तो i को 1 से बढ़ाएं
- j को 1 से बढ़ाएं
- i लौटाएं
C++ कार्यान्वयन
#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;
}
};
int main() {
Solution ob;
vector<int> v = {1,2}, v1 = {1,2,3};
cout << (ob.findContentChildren(v, v1));
return 0;
}
इनपुट
{1,2}, {1,2,3}
आउटपुट
2
