Вопрос

Вам дан массив people, где people[i] – это вес ith человека, и бесконечное количество лодок, каждая из которых может нести максимальный вес limit. Каждая лодка перевозит не более двух человек одновременно, при условии, что сумма веса этих людей не превышает limit.

Возвращает минимальное количество лодок для перевозки каждого человека.

Пример 1:

Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)

Пример 2:

Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3)

Пример 3:

Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5)

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

  • 1 <= people.length <= 5 * 104
  • 1 <= people[i] <= limit <= 3 * 104

Решение

Временная сложность O (n²)

Пространственная сложность O (n)

Временная сложность O (n Log n)

Пространственная сложность O(1)