Assign Cookies

Problem Overview

Title: Assign Cookies

The problem revolves around distributing cookies to children in such a way that a child is content if the cookie size is equal to or greater than the child's appetite. The goal is to maximize the number of children that can be satisfied with the available cookies.

The Assign Cookies problem is a classical example of using a Greedy Algorithm to derive an optimal solution.

Understanding the Problem

You are given two integer arrays:

• g[], representing the appetites of n children.
• s[], representing the m cookies available, where each cookie has a specific size.

Your task is to assign cookies to children such that the maximum number of children are content. A child i is content if they receive a cookie with a size greater than or equal to their appetite g[i].

Example

Input:

• g = [1,2,3]
• s = [1,1]

Output:

• 1

Explanation:

• You can initially assign one cookie of size 1 to one of the children with an appetite of 1, which leaves you with zero satisfying cookies for children with appetites 2 and 3.

Key DSA Concepts and Theory

Greedy Algorithm

A Greedy Algorithm is a simple, intuitive algorithm that is used in optimization problems. The algorithm makes the optimal choice at each step as it attempts to find the overall optimal way to solve the entire problem.

• Optimal Substructure: If an optimal solution can be constructed efficiently from optimal solutions of its subproblems.
• Greedy Choice Property: If a local optimum can be achieved by selecting the local optimum.

Sorting

Before applying a greedy approach here, sorting is an important preliminary step that helps ensure that we distribute resources (cookies) in the most efficient manner.

Solution Approach

The approach to solving the problem involves making sure that we use the smallest cookies to satisfy the least greedy children, allowing more cookies to potentially satisfy larger appetites. Here’s a detailed step-by-step approach:

1. Sort the Arrays: Start by sorting both the cookie sizes array (s) and the children's appetite array (g). Sorting helps us efficiently assign the smallest available cookie that can satisfy the smallest appetite.

2. Initialize Counters: Use two pointers or counters for both arrays to iterate through them.

3. Greedy Assignments: Iterate over the sorted arrays and try to assign a cookie to a child:

   • If the current cookie size s[j] can satisfy the current child's appetite g[i], assign the cookie and move to the next child (i++ and j++).
   • If s[j] is not sufficient for g[i], move to the next larger cookie (j++).

4. Count the Satisfied Children: Continue this process until we exhaust either the cookies or the children.

C++ Code

#include <iostream>
#include <vector>
#include <algorithm>

int findContentChildren(std::vector<int>& g, std::vector<int>& s) {
    std::sort(g.begin(), g.end());
    std::sort(s.begin(), s.end());
    
    int i = 0, j = 0;
    while (i < g.size() && j < s.size()) {
        if (s[j] >= g[i]) {
            i++;
        }
        j++;
    }
    return i;
}

int main() {
    std::vector<int> g = {1, 2, 3};
    std::vector<int> s = {1, 1};
    std::cout << findContentChildren(g, s) << std::endl; // Output: 1
    return 0;
}

Java Code

import java.util.Arrays;

public class AssignCookies {

    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);

        int i = 0, j = 0;
        while (i < g.length && j < s.length) {
            if (s[j] >= g[i]) {
                i++;
            }
            j++;
        }
        return i;
    }

    public static void main(String[] args) {
        AssignCookies ac = new AssignCookies();
        int[] g = {1, 2, 3};
        int[] s = {1, 1};
        System.out.println(ac.findContentChildren(g, s)); // Output: 1
    }
}

Time and Space Complexity Analysis

• Time Complexity: The dominant part of the code is the sort operation, which takes O(n log n) and O(m log m), where n is the number of children and m is the number of cookies. The subsequent iteration is linear, O(n + m), leading to a final time complexity of O(n log n + m log m).

• Space Complexity: The space complexity is O(1) because no auxiliary space is used other than a few variables to hold indices.

Common Mistakes to Avoid

• Not Sorting the Arrays: Forgetting to sort both arrays before attempting to assign cookies can lead to incorrect assignments and conclusions.
• Mismanagement of Counters: Ensure careful handling of indices to avoid off-by-one errors, especially in the loop condition.

Similar Problems on LeetCode

• Problem 435: Non-overlapping Intervals
• Problem 763: Partition Labels
• Problem 406: Queue Reconstruction by Height

Additional Resources and References

• Greedy Algorithms on GeeksforGeeks
• Sorting Algorithms Overview
• LeetCode Problem Discuss Forum for community solutions and discussions.

In conclusion, the Assign Cookies problem elegantly demonstrates how a greedy algorithm can be effectively utilized to derive the optimal solution by focusing on local maximum decisions to cater to overall optimal outcomes.