Premium

Сортировка

Раздать печенье

Раздать детям печенье так, чтобы все они были максимально довольны

Легкий

Постановка задачи

Описание (LeetCode - 455. Assign Cookies)

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

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

Если s[j] >= g[i], мы можем дать печенье j ребенку i, и он будет доволен. Наша задача - максимизировать количество довольных детей.

Нужно вернуть максимальное количество довольных детей.

Пример 1:

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

Результат:

1

Пояснение:

Мы можем отдать печенье размера 1 ребенку с жадностью 1. Оставшееся печенье размера 1 не подойдет детям с жадностью 2 или 3.

Пример 2:

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

Результат:

2

Пояснение:

Коэффициенты жадности детей равны 1 и 2. У нас есть 3 печенья, и их размеры достаточно велики, чтобы удовлетворить обоих детей.

Ограничения:

  • 1 <= g.length <= 3 * 10⁴
  • 0 <= s.length <= 3 * 10⁴
  • 1 <= g[i], s[j] <= 2³¹ - 1

Решение

Нам нужно раздать печенье так, чтобы удовлетворить как можно больше детей, но каждое печенье можно использовать только один раз. Эта задача отлично решается с помощью сортировки. Если отсортировать детей по жадности, а печенье - по размеру, мы сможем быстро определять, подходит ли текущее печенье текущему ребенку.

Идея решения:

Сначала мы удовлетворяем детей с самой маленькой жадностью. Если небольшое печенье подходит ребенку с малой жадностью, выгодно отдать его. Если оно не подходит, то не подойдет и более жадным детям, поэтому его можно пропустить.

Отсортируем оба массива по возрастанию. Затем будем идти двумя указателями:

  1. i указывает на текущего ребенка.
  2. j указывает на текущее печенье.

Если s[j] >= g[i], текущее печенье подходит ребенку. Мы увеличиваем ответ и переходим к следующему ребенку и следующему печенью.

Если s[j] < g[i], печенье слишком маленькое. Оно не подойдет этому ребенку и всем следующим, так как они еще более жадные. Мы переходим к следующему печенью.

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

Основные шаги:

  1. Сортируем g по возрастанию.
  2. Сортируем s по возрастанию.
  3. Идем по обоим массивам двумя указателями.
  4. Если печенье подходит ребенку, увеличиваем ответ и двигаем оба указателя.
  5. Если печенье слишком маленькое, двигаем только указатель печенья.
  6. Возвращаем количество довольных детей.

Рассмотрим пример:

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

Массивы уже отсортированы.

  1. Ребенок 1, печенье 1: подходит, ответ стал 1.
  2. Ребенок 2, печенье 1: не подходит, печенье пропускаем.
  3. Печенье закончилось.

Итоговый ответ равен 1.

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

Оценка сложности

Временная сложность

Сортировка массива g длины n занимает O(n log n). Сортировка массива s длины m занимает O(m log m). После этого мы выполняем один линейный проход.

Итоговая временная сложность: O(n log n + m log m).

Пространственная сложность

Если не учитывать память, необходимую для встроенной сортировки, мы храним только несколько переменных. Пространственная сложность составляет O(1).

Код решения

Приведем код решения.

func findContentChildren(g []int, s []int) int {
    sort.Ints(g)
    sort.Ints(s)
    i := 0
    j := 0
    count := 0
    for i < len(g) && j < len(s) {
        if s[j] >= g[i] {
            count++
            i++
        }
        j++
    }
    return count
}

Итоги

Задача Assign Cookies - хороший пример того, как сортировка превращает задачу распределения ресурсов в простой жадный алгоритм.

  1. Суть алгоритма: мы сортируем детей по жадности, печенье по размеру и всегда пытаемся удовлетворить самого нетребовательного оставшегося ребенка самым маленьким доступным печеньем.
  2. Эффективность:
    • Временная сложность: O(n log n + m log m), потому что нужно отсортировать оба массива.
    • Пространственная сложность: O(1), если не учитывать память встроенной сортировки.
  3. Граничные случаи:
    • Печенья нет: ответ 0.
    • Все печенья слишком маленькие: указатель печенья дойдет до конца, а счетчик довольных детей останется равным 0.
    • Печений больше, чем детей: алгоритм остановится, когда все дети будут удовлетворены.
  4. Оптимальное решение: сортировка дает порядок, в котором жадный выбор становится корректным. Мы не тратим большое печенье на ребенка, которому хватило бы меньшего, и поэтому максимизируем количество довольных детей.
Войдите чтобы отмечать прогресс