Problem Statement
Given an array of g (greed) where each g[i] represents the greed factor of the i-th child and an array of s (size) where each s[j] represents the size of the j-th cookie, your task is to assign cookies to children in such a way that maximizes the number of children who are content. A child is content if the size of the cookie assigned to them is at least as large as their greed factor.
Objective: Maximize the number of content children.
Examples
Example 1:
Input: greed factors = [1, 2, 3]
cookie sizes = [1, 1]
Output: 1
Explanation:
There are three children with greed factors 1, 2, and 3.
There are only two cookies of size 1 each.
Only one child with a greed factor of 1 can consume it(since the other children’s greed factors are greater than the cookie sizes).Example 2:
Input: greed factors = [1, 2]
cookie sizes = [1, 2, 3]
Output: 2
Explanation:
There are two children with greed factors 1, 2.
There are three cookies of size 1, 2, and 3 respectively.
Thus the first children will get the size of cookie of size 1,
and the second children will get the size of cookie of size 2.
So, both the children get the cookie.Different Approaches
1️⃣ Greedy Algorithm
Intuition:
The goal is to maximize the number of students who can be satisfied with the given cookies. By sorting both the students' greed factors and the cookie sizes, we can efficiently assign the smallest available cookie that satisfies each student's greed. We iterate through the arrays, assigning cookies to students until we either run out of students or cookies, ensuring the maximum number of satisfied students.
Approach:
- Sort both the children's greed and cookie sizes to efficiently pair the smallest cookies with the least greedy children.
- Use two pointers to iterate through the arrays, representing the smallest available cookie and the least greedy child.
- For each pair, check if the current cookie can satisfy the current child's greed.
- If a child's greed is satisfied, move to the next child; always move to the next cookie.
- The final count of satisfied children indicates the maximum number of children who can be content with the given cookies.
Dry Run:
Initialization:
+-----+-----+-----+-----+-----+
greed = | 1 | 5 | 3 | 3 | 4 |
(of +-----+-----+-----+-----+-----+
children) 0 1 2 3 4
+-----+-----+-----+-----+-----+-----+
cookies = | 4 | 2 | 1 | 2 | 1 | 3 |
size +-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
sort() both arrays:
+-----+-----+-----+-----+-----+
greed = | 1 | 3 | 3 | 4 | 5 |
(of +-----+-----+-----+-----+-----+
children) 0 1 2 3 4
+-----+-----+-----+-----+-----+-----+
cookies = | 1 | 1 | 2 | 2 | 3 | 4 |
size +-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
count = 0 (For the count of children who are assigned cookie).Iterate through greed array of children:
Iteration 1:
count = 0
+-----+-----+-----+-----+-----+
greed = | 1 | 3 | 3 | 4 | 5 |
(of +-----+-----+-----+-----+-----+
children) 0 1 2 3 4
^
|
i
+-----+-----+-----+-----+-----+-----+
cookies = | 1 | 1 | 2 | 2 | 3 | 4 |
size +-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
j
greed[i] == cookies[j]
Hence assign that cookie to the children,
i++, j++, count++Iteration 2:
count = 1
+-----+-----+-----+-----+-----+
greed = | 1 | 3 | 3 | 4 | 5 |
(of +-----+-----+-----+-----+-----+
children) 0 1 2 3 4
^
|
i
+-----+-----+-----+-----+-----+-----+
cookies = | 1 | 1 | 2 | 2 | 3 | 4 |
size +-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
j
Since greed[i] > cookie[j]
3 > 1
Keep on incrementing till greed[i] <= cookies[j]
+-----+-----+-----+-----+-----+-----+
cookies = | 1 | 1 | 2 | 2 | 3 | 4 |
size +-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
j
Since greed[i] == cookie[j]
3 == 3
Hence assign the cookie to the children,
i++, j++, count++Iteration 3:
count = 2
+-----+-----+-----+-----+-----+
greed = | 1 | 3 | 3 | 4 | 5 |
(of +-----+-----+-----+-----+-----+
children) 0 1 2 3 4
^
|
i
+-----+-----+-----+-----+-----+-----+
cookies = | 1 | 1 | 2 | 2 | 3 | 4 |
size +-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
j
Since greed[i] <= cookie[j]
3 <= 4
True
Hence assign the cookie of the children,
i++, j++, count++Loop Termination:
count = 3
+-----+-----+-----+-----+-----+
greed = | 1 | 3 | 3 | 4 | 5 |
(of +-----+-----+-----+-----+-----+
children) 0 1 2 3 4
^
|
i
+-----+-----+-----+-----+-----+-----+
cookies = | 1 | 1 | 2 | 2 | 3 | 4 |
size +-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5
^
|
j
Since j has crossed the bounds of the cookies aray which
means no more cookies can be assigned.
return count, which is 3.Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to find the maximum number of content children
int findMaximumCookieStudents(vector<int>& Student, vector<int>& Cookie) {
int n = Student.size();
int m = Cookie.size();
// Pointers
int l = 0, r = 0;
// Sorting of vectors
sort(Student.begin(), Student.end());
sort(Cookie.begin(), Cookie.end());
// Traverse through both arrays
while (l < n && r < m) {
/*If the current cookie can satisfy
the current student, move to the
next student*/
if (Cookie[r] >= Student[l]) {
l++;
}
// Move to next cookie
r++;
}
// Return the number of students who got cookies
return l;
}
};
int main() {
// Example input
vector<int> Student = {1, 2};
vector<int> Cookie = {1, 2, 3};
// Create a Solution object
Solution solution;
// Call the findMaximumCookieStudents function
int result = solution.findMaximumCookieStudents(Student, Cookie);
// Output the result
cout << "Number of students satisfied: " << result << endl;
return 0;
}
Complexity Analysis:
- Time Complexity:
O(N logN + M logM + min(N, M))whereNis the length of the student array, andMis the length of the cookies array. Sorting the student array takesO(N logN)time, and sorting the cookies array takesO(M logM)time.- After sorting, we iterate through the arrays up to
Mtimes, where M is the number of cookies. Each student and each cookie is considered at most once, making the time complexity of this iteration linear, which is O(M). Therefore, the total time complexity is O(N logN + M logM + M). - However with my calculation, the array of greed and cookie could also not equal. The algorithm uses a two-pointer technique to traverse both arrays, which runs in O(min(n, m)) because we traverse until one of the arrays is fully processed.
- So the overall Time complexity is
O(N logN) + O(M logM) + O(min(N, M)).
- So the overall Time complexity is
- After sorting, we iterate through the arrays up to
- Space Complexity:
O(1)no extra space used.