Distributing Cookies

Distributing Cookies

There are children with different hunger levels and cookies of different sizes. Each child can receive at most one cookie. A child is satisfied only if the cookie size is at least their hunger level. Find the maximum number of children that can be satisfied.

Example 1

Input: children = [1, 2, 3], cookies = [1, 1]

Output: 1

Explanation: the three children have hunger levels 1, 2 and 3. Both cookies have size 1, so only the child with hunger level 1 can be satisfied.

Example 2

Input: children = [1, 2], cookies = [1, 2, 3]

Output: 2

Explanation: there are two children with hunger levels 1 and 2. The number and sizes of the cookies are sufficient to satisfy both.

The least hungry child is the easiest to satisfy, so consider that child first. To preserve large cookies for hungrier children, give this child the smallest cookie that is still large enough. Repeat the same strategy with the least hungry remaining child until no suitable cookie remains.

The greedy strategy assigns the smallest sufficient cookie to the least hungry remaining child. Sorting children and cookies separately makes their size relationships easy to use. Start from the least hungry child and the smallest cookie, then count how many children can be satisfied.

#include <stdio.h>
#include <stdlib.h>

static int cmp(const void *p1, const void *p2) {
    int *num1 = (int *)p1;
    int *num2 = (int *)p2;
    return (*num1 > *num2) - (*num1 < *num2);
}

int distribute(int *children, int children_num, int *cookies, int cookies_num) {
    qsort(children, children_num, sizeof(children[0]), cmp);
    qsort(cookies, cookies_num, sizeof(cookies[0]), cmp);

    int child = 0;
    int cookie = 0;
    while (child < children_num && cookie < cookies_num) {
        if (children[child] <= cookies[cookie]) {
            child++;
        }
        cookie++;
    }
    return child;
}

int main(void) {
    int children[] = {1, 2};
    int children_num = sizeof(children) / sizeof(children[0]);
    int cookies[] = {1, 2, 3};
    int cookies_num = sizeof(cookies) / sizeof(cookies[0]);

    printf("%d\n", distribute(children, children_num, cookies, cookies_num));
    return 0;
}