Greedy: Assign maximum cookies

Problem Statement:

You are given 2 arrays, greed[] and cookie[].

greed[i] is the minimum cookie size wanted by ith child.

cookie[i] is the size of ith cookie.

You need to find the maximum number of children that can by satisfied by assigning them cookies.

Example:

Input: greed = [1, 2, 3] cookie = [1, 1]

Output: 1

Explanation: 

We have 3 children. 

1st child will need 1 cookie
2nd child will need 2 cookie
3rd child will need 3 cookie

We have 2 cookie, and can only satisfy 1 child.

Solution Explanation:

We will use greedy approach to solve the issue.

We will sort both the arrays.

Then check which children will be satisfied and return the result.

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> &greed, vector<int> &cookies) 
{
	sort(greed.begin(), greed.end());
    sort(cookies.begin(), cookies.end());
    
    int child = 0;
    for (int cookie = 0; child < greed.size() && cookie < cookies.size(); cookie ++) {
        if (cookies[cookie] >= greed[child]) {
            child ++;
        }
    }
    
    return child;
}

int main() 
{
	vector<int> greed = {1, 2, 3};
    vector<int> cookie = {1, 1};
  
    cout << solution(greed, cookie);
}

Output

1