Assign Cookies

Q: Какова временная сложность Assign Cookies?

Сортировка двух массивов требует O(n log n + m log m) , а последующий проход двумя указателями — O(n + m) , поэтому основную часть времени занимает сортировка. Сортировка на месте сохраняет дополнительную память на уровне O(1) , не считая памяти, используемой самой сортировкой.

Q: Почему жадный выбор работает для задачи Assign Cookies?

Пусть k — самое маленькое печенье, которое подходит наименее жадному ребёнку. Предположим, что в оптимальном распределении этому ребёнку досталось какое-то другое печенье. Поменяем их местами: ребёнок возьмёт k , а тот, кому досталось k , возьмёт другое печенье, которое не меньше k , поэтому он тоже останется сытым. Количество не изменится, значит, оптимальное распределение всегда может начинаться с жадного выбора, и тот же аргумент повторяется для оставшихся детей и печений.

ЛегкоЖадные алгоритмы Сортировка

+10

У каждого ребёнка i есть коэффициент жадности g[i]: минимальный размер печенья, который сделает его довольным. У каждого печенья j есть размер s[j]. Ребёнок доволен, если получает одно печенье, размер которого не меньше его коэффициента жадности. Каждый ребёнок может получить не более одного печенья, и каждое печенье может достаться не более чем одному ребёнку. Верните наибольшее число детей, которых можно сделать довольными.

Функция

findContentChildren(g: integer-array, s: integer-array) → integer

ginteger-array: уровень жадности каждого ребёнка, минимальный размер печенья, который он принимает
sinteger-array: размер каждого файла cookie
Возвращаетinteger: максимальное количество детей, каждый из которых может получить печенье размером не меньше своего коэффициента жадности

Ограничения

1 ≤ g.length, s.length ≤ 5000
1 ≤ g[i], s[j] ≤ 10⁵
Два массива могут иметь разную длину, и ни один из них не отсортирован.

Примеры

Ввод: g = [4, 2, 7]s = [3, 5, 1, 2]
Вывод: 2
Пояснение: После сортировки детям нужны 2, 4 и 7, а печенья имеют размеры 1, 2, 3 и 5. Печенье 2 достаётся ребёнку, которому нужно 2, а печенье 5 — ребёнку, которому нужно 4. Не осталось печенья, которое подошло бы ребёнку, которому нужно 7, поэтому ответ — 2.

+16 скрытых тестов при отправке

Дополнительный вопрос

Что, если у каждого ребёнка есть также печенье максимального размера, которое он согласен принять, так что печенье подходит только в определённом диапазоне? Тогда какому ожидающему ребёнку следует отдать каждое печенье?

Решение

Вопрос в том, какому ребёнку какое печенье дать. Перебор всех сочетаний приводит к взрывному росту числа вариантов, но одно жадное правило решает задачу: сначала обслужи наименее требовательного ребёнка и дай ему самое маленькое подходящее печенье. После сортировки обоих массивов это правило превращается в один проход с двумя указателями.

Самое маленькое подходящее печенье для каждого ребёнка

Верно, но не успевает на самых больших тестах

Идея

Расположите детей от наименее требовательного до самого требовательного. Для каждого ребёнка просмотрите все ещё не использованные печенья и выберите самое маленькое, которого достаточно. Если подходящего печенья нет, ребёнок останется голодным. В первом примере дети хотят получить 2, 4 и 7: ребёнок, которому нужно 2, получает печенье размером 2, ребёнок, которому нужно 4, получает печенье размером 5, а для ребёнка, которому нужно 7, ничего не остаётся.

Почему нужно выбирать самое маленькое подходящее печенье? Более крупное печенье может накормить любого ребёнка, которого может накормить более мелкое, и ещё кого-то. Если раздавать самое маленькое подходящее печенье, более крупные печенья останутся для более требовательных детей, которые идут позже, поэтому ты никогда не лишишь печенья ребёнка, которого мог накормить.

Недостаток — поиск. Каждый из n детей просматривает все m печений, поэтому при n = m = 5000 это 25 миллионов проверок — слишком медленно для самых больших тестов.

Алгоритм

Отсортируй коэффициенты жадности по возрастанию.
Храни флаг для каждого печенья, указывающий, использовано ли оно.
Для каждого ребёнка просматривай все печенья и запоминай наименьшее неиспользованное печенье, размер которого не меньше коэффициента жадности ребёнка.
Если такое печенье нашлось, пометь его как использованное и засчитай ребёнка как довольного.
Верни количество.

def findContentChildren(g, s):
    used = [False] * len(s)
    fed = 0
    for need in sorted(g):  # least greedy child first
        best = -1
        for j in range(len(s)):
            if not used[j] and s[j] >= need and (best == -1 or s[j] < s[best]):
                best = j
        if best != -1:
            used[best] = True
            fed += 1
    return fed

Отсортируйте оба и используйте два указателя

Идея

Приведённый выше алгоритм снова и снова ищет самое маленькое подходящее печенье. Отсортируйте и печенье — тогда поиск исчезнет: печенье будет идти в порядке возрастания размера, и первым вам встретится самое маленькое подходящее.

Просматривайте печенье от самого маленького к самому большому и держите один указатель — child, указывающий на наименее жадного из ожидающих детей. Если печенье не меньше g[child], ребёнок получает печенье, и указатель переходит к следующему ребёнку. Если оно меньше, то оно меньше и каждого из остальных ожидающих детей, поскольку они отсортированы, — значит, это печенье бесполезно, и вы переходите дальше.

В первом примере отсортированное печенье имеет размеры 1, 2, 3, 5, а отсортированные аппетиты равны 2, 4, 7. Печенье размером 1 слишком мало для аппетита 2. Печенье размером 2 достаётся ребёнку с аппетитом 2. Печенье размером 3 слишком мало для аппетита 4. Печенье размером 5 достаётся ребёнку с аппетитом 4. Указатель останавливается на 2 — это и есть ответ.

Каждый указатель движется только вперёд, поэтому обход занимает O(n + m), а основную часть времени занимают две сортировки. Сортировка на месте не требует дополнительных массивов.

Алгоритм

Отсортируйте g и s по возрастанию.
Установите child = 0 — это наименее жадный ребёнок, который всё ещё ждёт.
Для каждого печенья, начиная с самого маленького: если child всё ещё находится в пределах g и размер печенья не меньше g[child], увеличьте child на 1.
Верните child — количество накормленных детей.

def findContentChildren(g, s):
    g.sort()
    s.sort()
    child = 0  # the least greedy child still waiting
    for size in s:  # smallest cookie first
        if child < len(g) and size >= g[child]:
            child += 1
    return child

Ловушки и крайние случаи

Большинство неправильных ответов возникает из-за того, что сопоставление выполняется в неверном порядке или перемещается не тот указатель.

Дать ребёнку печенье большего размера, чем ему нужно. Если g = [1, 2] и s = [1, 3], то, отдав печенье 3 ребёнку, которому нужно 1, вы оставите голодным ребёнка, которому нужно 2, тогда как правильное распределение накормит обоих.
Перемещать указатель ребёнка, когда печенье слишком маленькое. Ребёнку всё ещё нужно печенье; бесполезно именно это печенье.
Забыть проверить границы для указателя ребёнка. Когда все дети накормлены, при проверке оставшихся печений нельзя выходить за конец g.
Сравнивать с помощью > вместо ≥. Печенья размером точно с коэффициент жадности достаточно.
Сортировать числа как текст. В JavaScript вызов sort() без компаратора ставит 10 перед 9.

Частые вопросы4

Какова временная сложность Assign Cookies?

Сортировка двух массивов требует O(n log n + m log m), а последующий проход двумя указателями — O(n + m), поэтому основную часть времени занимает сортировка. Сортировка на месте сохраняет дополнительную память на уровне O(1), не считая памяти, используемой самой сортировкой.

Почему жадный выбор работает для задачи Assign Cookies?

Пусть k — самое маленькое печенье, которое подходит наименее жадному ребёнку. Предположим, что в оптимальном распределении этому ребёнку досталось какое-то другое печенье. Поменяем их местами: ребёнок возьмёт k, а тот, кому досталось k, возьмёт другое печенье, которое не меньше k, поэтому он тоже останется сытым. Количество не изменится, значит, оптимальное распределение всегда может начинаться с жадного выбора, и тот же аргумент повторяется для оставшихся детей и печений.

Можешь начать с самого жадного ребёнка?

Да. Отсортируй оба массива, затем двигайся от самого большого печенья и самого жадного ребёнка: если самое большое оставшееся печенье подходит самому жадному оставшемуся ребёнку, накорми их обоих и передвинь оба указателя; если нет, этого ребёнка нельзя накормить никаким печеньем, поэтому пропусти его. Результат будет таким же за то же время.

Является ли Assign Cookies задачей на динамическое программирование?

Нет. Аргумент обмена показывает, что жадный выбор всегда безопасен, поэтому достаточно сортировки и одного прохода за O(n log n + m log m). Таблица по двум отсортированным массивам, заполненная по принципу таблицы для наибольшей общей подпоследовательности, тоже находит ответ, но требует O(n × m) времени для того же результата.

Python

def findContentChildren(g, s):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Ввод

g = [4, 2, 7]
s = [3, 5, 1, 2]

Ожидается