Лодки для спасения людей

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

people = [1, 2]
limit = 3

1

people = [3, 2, 2, 1]
limit = 3

3

people = [3, 5, 3, 4]
limit = 5

4

Решение

Мы могли бы перебрать все возможные пары людей, которые помещаются в одну лодку, и выбрать из них те, что минимизируют общее количество лодок. Проблема в том, что пары нельзя рассматривать независимо друг от друга: каждый человек может сесть только в одну лодку. Если человек A может поехать и с B, и с C, выбор одной пары блокирует другую.

Например, при весах [1, 2, 2, 3] и limit = 3 человек веса 1 может поехать с любым из двух человек веса 2. Какую пару мы выберем первой, влияет на то, кто останется и сколько лодок понадобится дальше. Поэтому решение "в лоб" требует перебора всех вариантов разбиения всего множества на группы размера 1-2, а не простого списка допустимых пар. Число таких разбиений растет экспоненциально.

Нам нужно другое решение. Здесь важно обратить внимание на условие: "Каждая лодка может перевозить максимум двух человек одновременно". Это ключевое наблюдение.

Представим, что мы взяли самого тяжелого человека и посадили в лодку. Если отправить его одного, мы потратим целую лодку. Логично подсадить к нему кого-то еще, чтобы сэкономить лодки.

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

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

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

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

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

1. l - на самого легкого оставшегося человека.
2. r - на самого тяжелого оставшегося человека.

Пока l <= r, мы выделяем лодку для человека r и проверяем, можно ли посадить вместе с ним человека l.

Если people[l] + people[r] <= limit, они едут вместе, и мы двигаем оба указателя.

Если сумма больше limit, самый тяжелый едет один, и мы двигаем только r.

В обоих случаях количество необходимых лодок увеличивается на 1.

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

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

1. Сортируем people по возрастанию.
2. Ставим l = 0, r = people.length - 1.
3. Пока l <= r, выделяем одну лодку.
4. Если people[l] + people[r] <= limit, двигаем l.
5. В любом случае двигаем r.
6. Возвращаем количество лодок.

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

people = [3, 2, 2, 1]
limit = 3

После сортировки:

people = [1, 2, 2, 3]

Проверяем пары:

1. Самый легкий 1, самый тяжелый 3. Сумма 4, они не помещаются. Человек 3 едет один.
2. Самый легкий 1, самый тяжелый 2. Сумма 3, они помещаются и едут вместе.
3. Остался человек 2. Он едет один.

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

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

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

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

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

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

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

Код решения

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

func numRescueBoats(people []int, limit int) int {
    sort.Ints(people)
    l := 0
    r := len(people) - 1
    boats := 0
    for l <= r {
        if people[l]+people[r] <= limit {
            l++
        }
        r--
        boats++
    }
    return boats
}

Итоги

Задача Boats to Save People - классический пример сочетания сортировки и паттерна двух указателей.

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